\input zb-basic
\input zb-ioport
\iteman{io-port 06099696}
\itemau{Janou\v{s}ek, Jan; Melichar, Bo\v{r}ivoj; Poliak, Martin}
\itemti{Tree compression pushdown automaton.}
\itemso{Kybernetika 48, No. 3, 429-452 (2012).}
\itemab
Summary: 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.
\itemrv{~}
\itemcc{}
\itemut{deterministic pushdown automata; Tree Compression Automaton; trees; indexing trees; arbology; compression}
\itemli{http://www.kybernetika.cz/content/2012/3/429}
\end