The Prague Stringology Club Workshop '96

Jan Holub

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 article: Article in PostScript Article in PDF
 PostScript   PDF