The Prague Stringology Club Workshop '98
Dynamic Programming for Reduced NFAs for Approximate String and Sequence Matching
| Abstract: |
| 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: |  |
 |
| PostScript |