Approximate Membership for Regular Languages modulo the Edit Distance

Antoine Ndione 1, 2 Aurélien Lemay 3, 1 Joachim Niehren 2, 1
1 LINKS - Linking Dynamic Data
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : 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.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2013, 487, pp.37-49
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00801970
Contributeur : Inria Mostrare <>
Soumis le : lundi 18 mars 2013 - 17:24:41
Dernière modification le : jeudi 11 janvier 2018 - 06:25:27
Document(s) archivé(s) le : jeudi 20 juin 2013 - 16:07:46

Fichier

0.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00801970, version 1

Citation

Antoine Ndione, Aurélien Lemay, Joachim Niehren. Approximate Membership for Regular Languages modulo the Edit Distance. Theoretical Computer Science, Elsevier, 2013, 487, pp.37-49. 〈hal-00801970〉

Partager

Métriques

Consultations de la notice

395

Téléchargements de fichiers

235