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

Boolean functioncomplexitymodel checkingpropositional logicquantified Boolean formulasatisfiability

Mathematics Subject Classification ID

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

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

• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• An algorithm to evaluate quantified Boolean formulae and its experimental evaluation
• 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?)
• Resolution for quantified Boolean formulas
• The intractability of resolution
• The polynomial-time hierarchy
• Theory and Applications of Satisfiability Testing

Cited in

(21)

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

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)