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

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

(9)

• 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
• Sublinear DTD validity
• An approximative inference method for solving ∃∀SO satisfiability problems
• Property testing of regular languages with applications to streaming property testing of visibly pushdown languages
• 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)