Approximate satisfiability and equivalence

DOI10.1137/070703776MaRDI QIDQ3068633zbMATH OpenOpenAlexFDO

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

\(\varepsilon\)-equivalence\(\varepsilon\)-satisfiabilitycontext-free languagesedit distance with movesequivalence testinginfinite regular languagesmonadic second-order formulasPSPACE-complete

Mathematics Subject Classification ID

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

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

(9)

• Approximate consistency for transformations on words and trees
• Sublinear DTD validity
• 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
• Structural Statistical Software Testing with Active Learning in a Graph
• Testing membership for timed automata
• Approximately satisfied properties of systems and simple language homomorphisms
• Property testing of regular languages with applications to streaming property testing of visibly pushdown languages

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)