Name
Abstract | ||
|---|---|---|
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 (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. In particular, for a given finite automaton A with n transitions, over an alphabet of r symbols, our algorithm operates in time O(n2r2q2( q+r)), where q is either the diameter of A (if A is deterministic), or the square of the number of states in A (if A is nondeterministic). Incidentally, we also obtain an upper bound on the edit distance of a regular language in terms of the automaton accepting the language. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.ic.2007.06.001 | Inf. Comput. |
Keywords | Field | DocType |
finite automaton,constraint system,distinct word,regular language.,algorithm,edit distance,smallest number,regular language,automaton,n transition,polynomial time complexity,r symbol,time o,levenshtein distance,finite automaton a,polynomial time,upper bound,time complexity | Edit distance,String-to-string correction problem,Discrete mathematics,Combinatorics,Wagner–Fischer algorithm,Jaro–Winkler distance,Levenshtein distance,Levenshtein automaton,Damerau–Levenshtein distance,Regular language,Mathematics | Journal |
Volume | Issue | ISSN |
205 | 9 | Information and Computation |
Citations | PageRank | References |
14 | 0.92 | 5 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stavros Konstantinidis | 1 | 283 | 31.10 |