Approximate satisfiability and equivalence

DOI10.1137/070703776zbMATH Open1207.68160OpenAlexW2052516237MaRDI QIDQ3068633FDOQ3068633

Authors: Eldar Fischer, Frédéric Magniez, Michel de Rougemont 

Publication date: 17 January 2011

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/070703776

Recommendations

• Approximate membership for regular languages modulo the edit distance
• Property testing of regular tree languages
• Automata, Languages and Programming
• Regular languages are testable with a constant number of queries
• Approximate consistency for transformations on words and trees

zbMATH Keywords

context-free languagesPSPACE-completeequivalence testingedit distance with movesinfinite regular languages\(\varepsilon\)-equivalencemonadic second-order formulas\(\varepsilon\)-satisfiability

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Grammars and rewriting systems (68Q42) Specification and verification (program logics, model checking, etc.) (68Q60)

Cited In (8)

• Approximate consistency for transformations on words and trees
• Approximate membership for regular languages modulo the edit distance
• Structural Statistical Software Testing with Active Learning in a Graph
• Testing membership for timed automata
• An approximative inference method for solving ∃∀SO satisfiability problems
• Sublinear DTD Validity
• Efficient Approximation of Well-Founded Justification and Well-Founded Domination
• Approximately satisfied properties of systems and simple language homomorphisms

This page was built for publication: Approximate satisfiability and equivalence

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