Approximate Satisfiability and Equivalence

DOI10.1137/070703776zbMath1207.68160OpenAlexW2052516237MaRDI QIDQ3068633

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

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) Specification and verification (program logics, model checking, etc.) (68Q60) Grammars and rewriting systems (68Q42) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (5)

Approximate consistency for transformations on words and trees ⋮ Approximate membership for regular languages modulo the edit distance ⋮ Testing membership for timed automata ⋮ Sublinear DTD Validity ⋮ Structural Statistical Software Testing with Active Learning in a Graph

This page was built for publication: Approximate Satisfiability and Equivalence