The Prague Stringology Club Workshop '96

Bruce W. Watson

A Collection of New Regular Grammar Pattern Matching Algorithms

A number of new algorithms for regular grammar pattern matching is presented. The new algorithms handle patterns specified by regular grammars - a generalization of multiple keyword pattern matching and single keyword pattern matching, both considered extensively in and [14, Chapter 4] and in [18]. Among the algorithms is a Boyer-Moore type algorithm for regular grammar pattern matching, answering a variant of an open problem posed by A.V. Aho in 1980 [2, p. 342]. Like the Boyer-Moore and Commentz-Walter algorithms, the generalized algorithm makes use of shift functions which can be precomputed and tabulated. It appears that many of the new algorithms can be efficiently implemented.

Download paper: Article in PostScript Article in PDF
 PostScript   PDF