Levenshtein automaton
In computer science, Levenshtein automata for a formal language are the family of finite state automata that can recognize the set V of all words in the language for which the Levenshtein distance to an arbitrary word w does not exceed a particular constant. Levenshtein transducers are extended Levenshtein automata that can in addition generate all strings in V at a fixed Levenshtein distance from a given w.
A Levenshtein automaton for W can be constructed in linear time with respect to the length of W, and can identify V in 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).
Since Levenshtein automata are finite-state machines, they can be described in (some) regular expression frameworks and finite-state algebra applies to them. In particular, Levenshtein transducers can be composed with other finite-state transducers.
Notes
 | This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. (September 2012) |
References
- Hassan, Ahmed; Noeman, Sara; Hassan, Hany (2008). "Language Independent Text Correction using Finite State Automata". Proc. IJCNLP. CiteSeerx: 10.1.1.138.6212.
{{cite conference}}: Unknown parameter|booktitle=ignored (|book-title=suggested) (help) - Mitankin, Petar N. (2005). Universal Levenshtein Automata. Building and Properties (PDF) (Thesis). Sofia University St. Kliment Ohridski.
- Schulz, Klaus U.; Mihov, Stoyan (2002). "Fast String Correction with Levenshtein-Automata". International Journal of Document Analysis and Recognition. 5 (1): 67–85. CiteSeerx: 10.1.1.16.652.
 | This computer science article is a stub. You can help Wikipedia by expanding it. |