Tomas Flouri¹, Jan Janousek² and Borivoj Melichar²

¹ 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

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