Approximate satisfiability and equivalence

DOI10.1137/070703776MaRDI QIDQ3068633zbMATHOpenAlexFDO

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

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)

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

Cited in

(8)

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

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)