UDC 004.635.3, DOI: 10.2298/CSIS1002331F

Subtree Matching by Pushdown Automata

Tomas Flouri1, Jan Janousek2 and Borivoj Melichar2

  1. Department of Computer Science and Engineering, Faculty of Electrical Engineering, Czech Technical University in Prague
    Karlovo nam. 13, 121 35 Prague 2, Czech Republic
    flourtom@fel.cvut.cz
  2. Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague
    Kolejn 550/2, 160 00 Prague 6, Czech Republic
    {Jan.Janousek,Borivoj.Melichar}@fit.cvut.cz

Abstract

Subtree matching is an important problem in Computer Science on which a number of tasks, such as mechanical theorem proving, term-rewriting, symbolic computation and nonprocedural programming languages are based on. A systematic approach to the construction of subtree pattern matchers by deterministic pushdown automata, which read subject trees in prefix and postfix notation, is presented. The method is analogous to the construction of string pattern matchers: for a given pattern, a nondeterministic pushdown automaton is created and is then determinised. In addition, it is shown that the size of the resulting deterministic pushdown automata directly corresponds to the size of the existing string pattern matchers based on finite automata.

Key words

subtree, subtree matching, pushdown automata

Digital Object Identifier (DOI)

https://doi.org/10.2298/CSIS1002331F

Publication information

Volume 7, Issue 2 (April 2010)
Advances in Languages, Related Technologies and Applications
Year of Publication: 2010
ISSN: 2406-1018 (Online)
Publisher: ComSIS Consortium

Full text

DownloadAvailable in PDF
Portable Document Format

How to cite

Flouri, T., Janousek, J., Melichar, B.: Subtree Matching by Pushdown Automata. Computer Science and Information Systems, Vol. 7, No. 2, 331-357. (2010), https://doi.org/10.2298/CSIS1002331F