Skip to Main content Skip to Navigation
Journal articles

Approximate Membership for Regular Languages modulo the Edit Distance

Antoine Mbaye Ndione 1 Aurélien Lemay 2, 1 Joachim Niehren 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download
Contributor : Inria Mostrare Connect in order to contact the contributor
Submitted on : Monday, March 18, 2013 - 5:24:41 PM
Last modification on : Wednesday, March 23, 2022 - 3:51:13 PM
Long-term archiving on: : Thursday, June 20, 2013 - 4:07:46 PM


Files produced by the author(s)



Antoine Mbaye Ndione, Aurélien Lemay, Joachim Niehren. Approximate Membership for Regular Languages modulo the Edit Distance. Theoretical Computer Science, Elsevier, 2013, 487, pp.37-49. ⟨10.1016/j.tcs.2013.03.004⟩. ⟨hal-00801970⟩



Record views


Files downloads