The complexity of variable minimal formulas

DOI10.1007/S11434-010-3127-2MaRDI QIDQ708020zbMATH OpenOpenAlexFDO

Authors Baowen Xu, Zhen-Yu Chen, Decheng Ding

Publication date 8 October 2010

Published in Chinese Science Bulletin (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11434-010-3127-2

zbMATH Keywords

minimal unsatisfiabilityprime implicationvariable minimal equivalencevariable minimal satisfiability

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Theory and Applications of Models of Computation
• The complexity of some subclasses of minimal unsatisfiable formulas.
• Extension and equivalence problems for clause minimal formulae
• Complexity results on minimal unsatisfiable formulas
• The Complexity of Boolean Formula Minimization

Cites work

• A fast counterexample minimization algorithm with refutation analysis and incremental SAT
• Applications of minimal unsatisfiable formulas to polynomially reduction for formulas
• scientific article; zbMATH DE number 1470716 (Why is no real title available?)
• Implication-Based Approximating Bounded Model Checking
• The complexity of facets (and some facets of complexity)
• The complexity of facets resolved
• The complexity of theorem-proving procedures
• The minimum equivalent DNF problem and shortest implicants
• Theory and Applications of Models of Computation
• Tools and Algorithms for the Construction and Analysis of Systems
• Two tractable subclasses of minimal unsatisfiable formulas

Cited in

(3)

• Variable and term removal from Boolean formulae
• Satisfiable formulas closed under replacement
• Automatically generating test data from a Boolean specification

This page was built for publication: The complexity of variable minimal formulas

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