Approximate Membership for Regular Languages ...
Type de document :
Compte-rendu et recension critique d'ouvrage
Titre :
Approximate Membership for Regular Languages modulo the Edit Distance
Auteur(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 ]
Titre de la revue :
Theoretical Computer Science
Pagination :
37-49
Éditeur :
Elsevier
Date de publication :
2013-02-15
ISSN :
1879-2294
Mot(s)-clé(s) en anglais :
automata
probabilistic algorithms
property testing
tegular word languages
probabilistic algorithms
property testing
tegular word languages
Discipline(s) HAL :
Informatique [cs]/Algorithme et structure de données [cs.DS]
Résumé en anglais : [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 ...
Lire la suite >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.Lire moins >
Lire la suite >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.Lire moins >
Langue :
Anglais
Vulgarisation :
Non
Collections :
Source :
Fichiers
- https://hal.inria.fr/hal-00801970/document
- Accès libre
- Accéder au document
- https://hal.inria.fr/hal-00801970/document
- Accès libre
- Accéder au document
- https://doi.org/10.1016/j.tcs.2013.03.004
- Accès libre
- Accéder au document
- https://doi.org/10.1016/j.tcs.2013.03.004
- Accès libre
- Accéder au document
- https://hal.inria.fr/hal-00801970/document
- Accès libre
- Accéder au document
- https://doi.org/10.1016/j.tcs.2013.03.004
- Accès libre
- Accéder au document
- https://doi.org/10.1016/j.tcs.2013.03.004
- Accès libre
- Accéder au document
- https://doi.org/10.1016/j.tcs.2013.03.004
- Accès libre
- Accéder au document
- https://doi.org/10.1016/j.tcs.2013.03.004
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- 0.pdf
- Accès libre
- Accéder au document
- j.tcs.2013.03.004
- Accès libre
- Accéder au document