Geodesic
Indexing Ordered Trees for (Nonlinear) Tree Pattern Matching by Pushdown Automata
Computer Science and Information Systems, Tome 9 (2012) no. 3.

Voir la notice de l'article provenant de la source Computer Science and Information Systems website

Trees are one of the fundamental data structures used in Computer Science. We present a new kind of acyclic pushdown automata, the tree pattern pushdown automaton and the nonlinear tree pattern pushdown automaton, constructed for an ordered tree. These automata accept all tree patterns and nonlinear tree patterns, respectively, which match the tree and represent a full index of the tree for such patterns. Given a tree with n nodes, the numbers of these distinct tree patterns and nonlinear tree patterns can be at most 2n-1+n and at most (2+v)n-1+2, respectively, where v is the maximal number of nonlinear variables allowed in nonlinear tree patterns. The total sizes of nondeterministic versions of the two pushdown automata are O(n) and O(n2), respectively. We discuss the time complexities and show timings of our implementations using the bit-parallelism technique. The timings show that for a given tree the running time is linear to the size of the input pattern.
Keywords: Tree patternmatching, nonlinear tree patternmatching, indexing trees, pushdown automata 
@article{CSIS_2012_9_3_a7,
     author = {Jan Travn{\i}cek and Jan Janousek and Borivoj Melichar},
     title = {Indexing {Ordered} {Trees} for {(Nonlinear)} {Tree} {Pattern} {Matching} by {Pushdown} {Automata}},
     journal = {Computer Science and Information Systems},
     publisher = {mathdoc},
     volume = {9},
     number = {3},
     year = {2012},
     url = {http://geodesic.mathdoc.fr/item/CSIS_2012_9_3_a7/}
}
TY  - JOUR
AU  - Jan Travnıcek
AU  - Jan Janousek
AU  - Borivoj Melichar
TI  - Indexing Ordered Trees for (Nonlinear) Tree Pattern Matching by Pushdown Automata
JO  - Computer Science and Information Systems
PY  - 2012
VL  - 9
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CSIS_2012_9_3_a7/
ID  - CSIS_2012_9_3_a7
ER  - 
%0 Journal Article
%A Jan Travnıcek
%A Jan Janousek
%A Borivoj Melichar
%T Indexing Ordered Trees for (Nonlinear) Tree Pattern Matching by Pushdown Automata
%J Computer Science and Information Systems
%D 2012
%V 9
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CSIS_2012_9_3_a7/
%F CSIS_2012_9_3_a7
Jan Travnıcek; Jan Janousek; Borivoj Melichar. Indexing Ordered Trees for (Nonlinear) Tree Pattern Matching by Pushdown Automata. Computer Science and Information Systems, Tome 9 (2012) no. 3. http://geodesic.mathdoc.fr/item/CSIS_2012_9_3_a7/