The Prague Stringology Club Workshop '96
Reduced Nondeterministic Finite Automata for Approximate String Matching
| Abstract: |
| We will show how to reduce the number of states of nondeterministic finite automata for approximate string matching with k mismatches and nondeterministic finite automata for approximate string matching with k differences in the case when we do not need to know how many mismatches or differences are in the found string. Also we will show impact of this reduction on Shift-Or based algorithms. |
| Download paper: |  |
 |
| PostScript |