Currently displaying 1 – 1 of 1

Showing per page

Order by Relevance | Title | Year of publication

Tree compression pushdown automaton

Jan JanoušekBořivoj MelicharMartin Poliak — 2012

Kybernetika

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 for storing...

Page 1

Download Results (CSV)