The complexity of model checking for Boolean formulas

DOI10.1142/S0129054110007258MaRDI QIDQ3569272zbMATH OpenFDO

Authors Henning Schnoor

Publication date 18 June 2010

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0129054110007258

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• The complexity of model checking for circumscriptive formulae
• Boolean functions as models for quantified Boolean formulas
• On the complexity of the model checking problem
• scientific article; zbMATH DE number 3978379
• The Complexity of Very Simple Boolean Formulas with Applications

Cites work

• Circuits, matrices, and nonassociative computation
• Gap-languages and log-time complexity classes
• scientific article; zbMATH DE number 1161568 (Why is no real title available?)
• On the Structure of Polynomial Time Reducibility
• Satisfiability problems for propositional calculi
• The complexity of the descriptiveness of Boolean circuits over different sets of gates

Cited in

(5)

• The complexity of model checking for circumscriptive formulae
• Complexity of model checking for cardinality-based belief revision operators
• Boolean functions as models for quantified Boolean formulas
• On the applicability of Post's lattice
• The complexity of circumscriptive inference in Post's lattice

This page was built for publication: The complexity of model checking for Boolean formulas

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