The Prague Stringology Club Workshop '97

Bruce W. Watson

A Boyer-Moore (or Watson-Watson) Type Algorithm for Regular Tree Pattern Matching

In this paper, I outline a new algorithm for regular tree pattern matching. The Boyer-Moore family of string pattern matching algorithm sare considered to be among the most efficient. The Boyer-Moore idea of a shift distance was generalized by Commentz-Walter for multiple keywords, and generalizations for regular expressions have also been found. The existence of a further generalization to tree pattern matching was first mentioned in the statements accompanying my dissertation.

Download paper: Article in PostScript Article in PDF
 PostScript   PDF