Indexing Ordered Trees for (Nonlinear) Tree Pattern Matching by Pushdown Automata

Jan Travnıcek1, Jan Janousek1 and Borivoj Melichar1

  1. Faculty of Information Technology, Czech Technical University in Prague
    Thakurova 9, 160 00 Prague 6, Czech Republic
    {travnja3, Jan.Janousek, melichar}@fit.cvut.cz

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

Key words

Tree patternmatching, nonlinear tree patternmatching, indexing trees, pushdown automata

Digital Object Identifier (DOI)

https://doi.org/10.2298/CSIS111220024T

Publication information

Volume 9, Issue 3 (September 2012)
Special Issue on Advances in Computer Languages, Modeling and Agents
Year of Publication: 2012
ISSN: 1820-0214 (Print) 2406-1018 (Online)
Publisher: ComSIS Consortium

Full text

DownloadAvailable in PDF
Portable Document Format

How to cite

Travnıcek, J., Janousek, J., Melichar, B.: Indexing Ordered Trees for (Nonlinear) Tree Pattern Matching by Pushdown Automata. Computer Science and Information Systems, Vol. 9, No. 3, 1125-1154. (2012)