Computing the edit distance of a regular language
S. Konstantinidis
The edit distance (or Levenshtein distance)
between two words is the smallest number of substitutions,
insertions, and deletions of symbols that can be used to transform
one of the words into the other. In this paper we consider the
problem of computing the edit distance of a regular language (also
known as constraint system), that is, the set of words accepted by a
given finite automaton. This quantity is the smallest edit distance
between any pair of distinct words of the language. We show that the
problem is of polynomial time complexity. We distinguish two cases
depending on whether the given automaton is deterministic or
nondeterministic. In the latter case the time complexity is higher.
Incidentally, we also obtain an upper bound on the edit distance of
a regular language in terms of the automaton accepting the language.