Tree template matching in ranked ordered trees by pushdown automata

Tomáš Flouri*, Jan Janoušek, Bořivoj Melichar, Costas S. Iliopoulos, Solon P. Pissis

*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

We consider the problem of tree template matching in ranked ordered trees, and propose a solution based on the bottom-up technique. Specifically, we transform the tree pattern matching problem to a string matching problem, by transforming the tree template and the subject tree to strings representing their postfix notation, and then use pushdown automata as the computational model. The method is analogous to the construction of string pattern matchers. The given tree template is preprocessed once, by constructing a nondeterministic pushdown automaton, which is then transformed to the equivalent deterministic one. Although we prove that the space required for preprocessing is exponential to the size of the tree template in the general case, the space required for a specific class of tree templates is linear. The time required for the searching phase is linear to the size of the subject tree in both cases.

Original languageEnglish
Title of host publicationImplementation and Application of Automata - 16th International Conference, CIAA 2011, Proceedings
Pages273-281
Number of pages9
DOIs
Publication statusPublished - 11 Aug 2011
Externally publishedYes
Event16th International Conference on Implementation and Application of Automata, CIAA 2011 - Blois, France
Duration: 13 Jul 201116 Jul 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6807 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference16th International Conference on Implementation and Application of Automata, CIAA 2011
CountryFrance
CityBlois
Period13/07/1116/07/11

Fingerprint

Dive into the research topics of 'Tree template matching in ranked ordered trees by pushdown automata'. Together they form a unique fingerprint.

Cite this