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 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 then it is 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.