A Boyer-Moore (or Watson-Watson) Type Algorithm for Regular Tree Pattern Matching.
Bruce W. Watson · 1995
Abstract. In this paper, I outline a new algorithm for regular tree pattern matching. The Boyer-Moore family of string pattern matching algorithms are considered to be among the most ecient. The Boyer-Moore idea of a shift dis-tance was generalized by Commentz-Walter for multiple keywords, and general-izations for regular expressions have also been found. The existence of a further generalization to tree pattern matching was rst mentioned in the statements accompanying my dissertation, [Wats95]. Key words: tree pattern matching, tree parsing, code selection, Boyer-Moore