The Prague Stringology Club Workshop '96
A Collection of New Regular Grammar Pattern Matching Algorithms
| Abstract: |
| 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: |  |
 |
| PostScript |