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.
| Property | Value |
|---|
| dbpprop:abstract
|
- 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). The construction operation for the Levenshtein automaton reflects the composition of a finite state transducer with the word. A probabilistic relative of the Levenshtein automaton is the Hidden Markov model.
|
| dbpprop:hasPhotoCollection
| |
| dbpprop:reference
| |
| rdf:type
| |
| rdfs:comment
|
- 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.
|
| rdfs:label
| |
| owl:sameAs
| |
| skos:subject
| |
| foaf:page
| |
| is dbpprop:redirect
of | |
| is owl:sameAs
of | |
![[RDF Data]](/statics/sw-cube.png)
