The Prague Stringology Club Workshop '98

Jan Holub

Dynamic Programming for Reduced NFAs for Approximate String and Sequence Matching

We present a new simulation method for the reduced nondeterministic finite automata (NFAs) for the approximate string and sequence matching using the Levenshtein and generalized Levenshtein distances. These reduced NFAs are used in case that we are interested only in all occurrences of a pattern in an input text such that the edit distance between the pattern and the found strings is less or equal to a given k and we are not interested in the values of these edit distances. The presented simulation method is based on the dynamic programming.

Download paper: Article in PostScript Article in PDF
 PostScript   PDF