Name
Abstract | ||
|---|---|---|
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 2(n-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(n(2)), 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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.2298/CSIS111220024T | COMPUTER SCIENCE AND INFORMATION SYSTEMS |
Keywords | Field | DocType |
Tree pattern matching,nonlinear tree pattern matching,indexing trees,pushdown automata | Discrete mathematics,Data mining,Range tree,AVL tree,Computer science,K-ary tree,Algorithm,Tree structure,Segment tree,Fractal tree index,Search tree,Interval tree | Journal |
Volume | Issue | ISSN |
9 | SP3 | 1820-0214 |
Citations | PageRank | References |
0 | 0.34 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jan Travnicek | 1 | 1 | 1.72 |
| Jan Janousek | 2 | 23 | 4.80 |
| Borivoj Melichar | 3 | 72 | 16.63 |