Andreas Neumann and Helmut Seidl. Locating Matches of Tree Patterns in Forests. In Vikraman Arvind and Ramaswamy Ramanujam, editors, Foundations of Software Technology and Theoretical Computer Science, volume 1530 of Lecture Notes in Computer Science, pages 134-145, Chennai, India, December 1998. Springer.

We deal with matching and locating of patterns in forests of variable arity. A pattern consists of a structural and a contextual condition for subtrees of a forest, both of which are given as tree or forest regular languages. We use the notation of constraint systems to uniformly specify both kinds of conditions. In order to implement pattern matching we introduce the class of pushdown forest automata. We identify a special class of contexts such that not only pattern matching but also locating all of a forest's subtrees matching in context can be performed in a single traversal. We also give a method for computing the reachable states of an automaton in order to minimize the size of transition tables.

Download: PDF Reference: Bibtex The original publication is available at