Approximate membership for regular languages modulo the edit distance

DOI10.1016/j.tcs.2013.03.004zbMath1293.68307OpenAlexW1995386090MaRDI QIDQ387000

Joachim Niehren, Antoine Ndione, Aurélien Lemay

Publication date: 11 December 2013

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.03.004

zbMATH Keywords

probabilistic algorithmsproperty testingnon-deterministic finite automataregular word languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Randomized algorithms (68W20)

Related Items

Approximate consistency for transformations on words and trees, Sublinear DTD Validity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Regular Languages are Testable with a Constant Number of Queries
• The Cost of Traveling between Languages
• Approximate Satisfiability and Equivalence
• Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity
• Testing Membership in Languages that Have Small Width Branching Programs
• Property testing and its connection to learning and approximation
• Approximate Structural Consistency
• Robust Characterizations of Polynomials with Applications to Program Testing
• Chrobak Normal Form Revisited, with Applications
• Abstract Combinatorial Programs and Efficient Property Testers
• Every property of hyperfinite graphs is testable