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.
| Property | Value |
|---|
| dbpedia-owl:abstract
|
- 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. Experimental implementations of the Levenshtein automaton exist in Python and Java
|
| dbpedia-owl:wikiPageExternalLink
| |
| dcterms:subject
| |
| rdfs:comment
|
- 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.
|
| rdfs:label
| |
| owl:sameAs
| |
| foaf:page
| |
| is dbpedia-owl:wikiPageRedirects
of | |
| is owl:sameAs
of | |
| is foaf:primaryTopic
of | |
