Boolean functions as models for quantified Boolean formulas

DOI10.1007/S10817-007-9067-0MaRDI QIDQ2642467zbMATH OpenOpenAlexFDO

Authors Hans Kleine Büning, K. Subramani, Xishun Zhao

Publication date 17 August 2007

Published in Journal of Automated Reasoning (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10817-007-9067-0

zbMATH Keywords

complexitymodel checkingBoolean functionsatisfiabilityquantified Boolean formulapropositional logic

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Classical propositional logic (03B05) Specification and verification (program logics, model checking, etc.) (68Q60) Boolean functions (06E30)

Recommendations

• Logic versus Approximation
• Theory and Applications of Satisfiability Testing
• Nested Boolean functions as models for quantified Boolean formulas
• Theory and Applications of Satisfiability Testing
• The complexity of model checking for Boolean formulas

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1470716 (Why is no real title available?)
• scientific article; zbMATH DE number 1765680 (Why is no real title available?)
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• An algorithm to evaluate quantified Boolean formulae and its experimental evaluation
• Resolution for quantified Boolean formulas
• The intractability of resolution
• The polynomial-time hierarchy
• Theory and Applications of Satisfiability Testing

Cited in

(21)

• scientific article; zbMATH DE number 5719280 (Why is no real title available?)
• Quantified maximum satisfiability
• Database Support for Data Mining Applications
• From LTL to unambiguous Büchi automata via disambiguation of alternating automata
• Logic versus Approximation
• Function representation of the Boolean-valued universe
• scientific article; zbMATH DE number 2033418 (Why is no real title available?)
• Encoding nested Boolean functions as quantified Boolean formulas
• Boolean Models and Simultaneous Inequalities
• Boolean valued models and incomplete specifications
• Function representation of the Boolean-valued universe
• The complexity of model checking for Boolean formulas
• Solution validation and extraction for QBF preprocessing
• A Unified Framework for Certificate and Compilation for QBF
• Lost in translation: language independence in propositional logic -- application to belief change
• scientific article; zbMATH DE number 1471980 (Why is no real title available?)
• Alternative definitions of Boolean functions and relations
• Nested Boolean functions as models for quantified Boolean formulas
• Theory and Applications of Satisfiability Testing
• Theory and Applications of Satisfiability Testing
• Minimal False Quantified Boolean Formulas

Describes a project that uses

Uses Software

• QUBE

This page was built for publication: Boolean functions as models for quantified Boolean formulas

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