Indexing ordered trees for (nonlinear) tree pattern matching

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F12%3A00196583" target="_blank" >RIV/68407700:21240/12:00196583 - isvavai.cz</a>
Result on the web
<a href="http://www.comsis.org/archive.php?show=vol0903" target="_blank" >http://www.comsis.org/archive.php?show=vol0903</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.2298/CSIS111220024T" target="_blank" >10.2298/CSIS111220024T</a>

Result language
angličtina
Original language name
Indexing ordered trees for (nonlinear) tree pattern matching
Original language description
A new kind of acyclic pushdown automata for an ordered tree is presented. The tree pattern pushdown automaton and the nonlinear tree pattern pushdown automaton represent a complete index of the tree for tree patterns and nonlinear tree patterns, respectively. Given a tree with n nodes, the numbers of distinct tree patterns and nonlinear tree patterns whichmatch the tree can be atmost 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-parallelismtechnique. The timings show that for a given tree the running time is linear to the size of the input pattern. The presented pushdown automata are input-driven and therefore can be also determinised.
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
IN - Informatics
OECD FORD branch
—

Publication year
2012
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)