Skip to Main content Skip to Navigation
Journal articles

Approximate Membership for Regular Languages modulo the Edit Distance

Antoine 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

https://hal.inria.fr/hal-00801970
Contributor : Inria Mostrare <>
Submitted on : Monday, March 18, 2013 - 5:24:41 PM
Last modification on : Tuesday, March 30, 2021 - 11:48:39 AM
Long-term archiving on: : Thursday, June 20, 2013 - 4:07:46 PM

File

0.pdf
Files produced by the author(s)

Identifiers

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. ⟨10.1016/j.tcs.2013.03.004⟩. ⟨hal-00801970⟩

Share

Metrics

Record views

678

Files downloads

583