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

property testingprobabilistic algorithmsnon-deterministic finite automataregular 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

• 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?)
• Abstract Combinatorial Programs and Efficient Property Testers
• Approximate Structural Consistency
• Approximate satisfiability and equivalence
• 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
• 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

(5)

• Approximating Language Edit Distance Beyond Fast Matrix Multiplication: Ultralinear Grammars Are Where Parsing Becomes Hard!
• Sublinear DTD validity
• Automata, Languages and Programming
• Approximate consistency for transformations on words and trees
• Approximate satisfiability and equivalence

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)