Geodesic
Tree compression pushdown automaton
Kybernetika, Tome 48 (2012) no. 3, pp. 429-452

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

A new kind of a deterministic pushdown automaton, called a Tree Compression Automaton, is presented. The tree compression automaton represents a complete compressed index of a set of trees for subtrees and accepts all subtrees of given trees. The algorithm for constructing our pushdown automaton is incremental. For a single tree with $n$ nodes, the automaton has at most $n+1$ states, its transition function cardinality is at most $4n$ and there are $2n+1$ pushdown store symbols. If hashing is used for storing automaton's transitions, thus removing a factor of $log n$, the construction of the automaton takes linear time and space with respect to the length $n$ of the input tree(s). Our pushdown automaton construction can also be used for finding all subtree repeats without augmenting the overall complexity.
Classification : 05C05, 68Q68
Keywords: trees; pushdown automata; compression; indexing trees; arbology 
@article{KYB_2012__48_3_a5,
     author = {Janou\v{s}ek, Jan and Melichar, Bo\v{r}ivoj and Poliak, Martin},
     title = {Tree compression pushdown automaton},
     journal = {Kybernetika},
     pages = {429--452},
     publisher = {mathdoc},
     volume = {48},
     number = {3},
     year = {2012},
     mrnumber = {2975798},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2012__48_3_a5/}
}
TY  - JOUR
AU  - Janoušek, Jan
AU  - Melichar, Bořivoj
AU  - Poliak, Martin
TI  - Tree compression pushdown automaton
JO  - Kybernetika
PY  - 2012
SP  - 429
EP  - 452
VL  - 48
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/KYB_2012__48_3_a5/
LA  - en
ID  - KYB_2012__48_3_a5
ER  - 
%0 Journal Article
%A Janoušek, Jan
%A Melichar, Bořivoj
%A Poliak, Martin
%T Tree compression pushdown automaton
%J Kybernetika
%D 2012
%P 429-452
%V 48
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/KYB_2012__48_3_a5/
%G en
%F KYB_2012__48_3_a5
Janoušek, Jan; Melichar, Bořivoj; Poliak, Martin. Tree compression pushdown automaton. Kybernetika, Tome 48 (2012) no. 3, pp. 429-452. http://geodesic.mathdoc.fr/item/KYB_2012__48_3_a5/