Approximate membership for regular languages modulo the edit distance

DOI10.1016/J.TCS.2013.03.004MaRDI QIDQ387000zbMATH OpenOpenAlexFDO

Authors Antoine Ndione, Aurélien Lemay, Joachim Niehren

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

non-deterministic finite automataprobabilistic algorithmsproperty testingregular word languages

Mathematics Subject Classification ID

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

Recommendations

• Computing the edit distance of a regular language
• Property testing of regular tree languages
• Approximate satisfiability and equivalence
• Automata, Languages and Programming
• A sublinear algorithm for weakly approximating edit distance

Cites work

• Abstract Combinatorial Programs and Efficient Property Testers
• Approximate satisfiability and equivalence
• Approximate Structural Consistency
• Approximating the influence of monotone Boolean functions in \(O(\sqrt{n})\) query complexity
• Chrobak normal form revisited, with applications
• Every property of hyperfinite graphs is testable
• scientific article; zbMATH DE number 1819631 (Why is no real title available?)
• scientific article; zbMATH DE number 1241385 (Why is no real title available?)
• scientific article; zbMATH DE number 2119722 (Why is no real title available?)
• Property testing and its connection to learning and approximation
• Property testing. A learning theory perspective
• Regular languages are testable with a constant number of queries
• Robust Characterizations of Polynomials with Applications to Program Testing
• Testing Membership in Languages that Have Small Width Branching Programs
• The Cost of Traveling between Languages

Cited in

(6)

• Approximate consistency for transformations on words and trees
• Sublinear DTD validity
• Approximate satisfiability and equivalence
• Approximating Language Edit Distance Beyond Fast Matrix Multiplication: Ultralinear Grammars Are Where Parsing Becomes Hard!
• Automata, Languages and Programming
• Property testing of regular languages with applications to streaming property testing of visibly pushdown languages

This page was built for publication: Approximate membership for regular languages modulo the edit distance

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q387000)