Tree indexing by pushdown automata and subtree repeats
Tomáš Flouri, Costas S. Iliopoulos, Jan Janoušek, Bořivoj Melichar, Solon P. Pissis · Research Portal (King's College London) · 2011
We consider the problem of finding all subtree repeats in a given unranked ordered tree. We show a new, elegant, and simple method, which is based on the construction of a tree indexing structure called the subtree pushdown automaton. We propose a solution for computing all subtree repeats from the deterministic subtree pushdown automaton constructed over the subject tree. The method we present is directly analogous to the relationship between string deterministic suffix automata and factor repeats in a given string.