On Tree Pattern Matching by Pushdown Automata
DOI:
https://doi.org/10.14311/1113Keywords:
tree, tree pattern, pushdown automaton, tree pattern matchingAbstract
Tree pattern matching is an important operation in Computer Science on which a number of tasks such as mechanical theorem proving, term-rewriting, symbolic computation and non-procedural programming languages are based on. Work has begun on a systematic approach to the construction of tree pattern matchers by deterministic pushdown automata which read subject trees in prefix notation. The method is analogous to the construction of string pattern matchers: for given patterns, a non-deterministic pushdown automaton is created and then it is determinised. In this first paper, we present the proposed non-deterministic pushdown automaton which will serve as a basis for the determinisation process, and prove its correctness.Downloads
Download data is not yet available.
Downloads
Published
2009-01-02
How to Cite
Flouri, T. (2009). On Tree Pattern Matching by Pushdown Automata. Acta Polytechnica, 49(2). https://doi.org/10.14311/1113
Issue
Section
Articles