Displaying similar documents to “Advanced Indexing Technique for Temporal Data”

Tree compression pushdown automaton

Jan Janoušek, Bořivoj Melichar, Martin Poliak (2012)

Kybernetika

Similarity:

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 4 n and there are 2 n + 1 pushdown store symbols. If hashing is used...