Levenshtein automaton

From Wikipedia, the free encyclopedia

You have new messages (last change).

In computer science, Levenshtein automata are a family of finite state automata that can recognize the set V of all words in a formal language for which the Levenshtein distance to an arbitrary word W does not exceed a particular constant. A Levenshtein automaton for W can be constructed in linear time proportional to the length of W, and can identify V in much less time than would be needed if the Levenshtein distance to W was calculated for each word in the language (a problem with quadratic time complexity).

[edit] References

 This computer-related article is a stub. You can help Wikipedia by expanding it.
Retrieved from "http://en.wikipedia.org../../../l/e/v/Levenshtein_automaton.html"
In other languages