Approximate Membership for Regular Languages ...
Document type :
Compte-rendu et recension critique d'ouvrage
Title :
Approximate Membership for Regular Languages modulo the Edit Distance
Author(s) :
Ndione, Antoine [Auteur]
Linking Dynamic Data [LINKS ]
Lemay, Aurélien [Auteur]
Linking Dynamic Data [LINKS ]
Niehren, Joachim [Auteur]
Linking Dynamic Data [LINKS ]
Linking Dynamic Data [LINKS ]
Lemay, Aurélien [Auteur]
Linking Dynamic Data [LINKS ]
Niehren, Joachim [Auteur]
Linking Dynamic Data [LINKS ]
Journal title :
Theoretical Computer Science
Pages :
37-49
Publisher :
Elsevier
Publication date :
2013-02-15
ISSN :
1879-2294
English keyword(s) :
automata
probabilistic algorithms
property testing
tegular word languages
probabilistic algorithms
property testing
tegular word languages
HAL domain(s) :
Informatique [cs]/Algorithme et structure de données [cs.DS]
English abstract : [en]
We present a probabilistic algorithm for testing approximate membership of words to regular languages modulo the edit distance. The time complexity of our algorithm, which is independent of the size of the input word, is ...
Show more >We present a probabilistic algorithm for testing approximate membership of words to regular languages modulo the edit distance. The time complexity of our algorithm, which is independent of the size of the input word, is polynomial in the size of the input automaton and the inverse error precision. All previous property testing algorithms for regular languages, whether they consider approximations modulo the Hamming distance or the edit distance with moves, run in exponential time if not fixing one of these parameters.Show less >
Show more >We present a probabilistic algorithm for testing approximate membership of words to regular languages modulo the edit distance. The time complexity of our algorithm, which is independent of the size of the input word, is polynomial in the size of the input automaton and the inverse error precision. All previous property testing algorithms for regular languages, whether they consider approximations modulo the Hamming distance or the edit distance with moves, run in exponential time if not fixing one of these parameters.Show less >
Language :
Anglais
Popular science :
Non
Collections :
Source :
Files
- https://hal.inria.fr/hal-00801970/document
- Open access
- Access the document
- https://hal.inria.fr/hal-00801970/document
- Open access
- Access the document
- https://doi.org/10.1016/j.tcs.2013.03.004
- Open access
- Access the document
- https://doi.org/10.1016/j.tcs.2013.03.004
- Open access
- Access the document
- https://hal.inria.fr/hal-00801970/document
- Open access
- Access the document
- https://doi.org/10.1016/j.tcs.2013.03.004
- Open access
- Access the document
- https://doi.org/10.1016/j.tcs.2013.03.004
- Open access
- Access the document
- https://doi.org/10.1016/j.tcs.2013.03.004
- Open access
- Access the document
- https://doi.org/10.1016/j.tcs.2013.03.004
- Open access
- Access the document
- document
- Open access
- Access the document
- 0.pdf
- Open access
- Access the document
- j.tcs.2013.03.004
- Open access
- Access the document