Indexing trees by pushdown automata for nonlinear tree pattern matching
Jan Trávníček, Jan Janoušek, B. Melichar · 2011
Abstract—A new kind of an acyclic pushdown automaton for an ordered tree is presented.The nonlinear tree pattern pushdown automaton represents a complete index of the tree for nonlinear tree patterns and accepts all nonlinear tree patterns which match the tree. Given a tree with n nodes, the number of such nonlinear tree patterns is O((2+v) n), where v is the number of variables in the patterns. We discuss time and space complexities of the nondeterministic nonlinear tree pattern pushdown automaton and a way of its implementation. The presented pushdown automaton is input–driven and therefore can be determinised. I.