Variable and term removal from Boolean formulae

DOI10.1016/S0166-218X(96)00028-5zbMath0879.94041MaRDI QIDQ1363769

Peter L. Hammer, Yves Cramer, Oya Ekin

Publication date: 26 January 1998

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

Boolean functions; disjunctive normal forms; VD-sets; VF-sets

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

Related Items

Backdoor sets of quantified Boolean formulas, Correlations between Horn fractions, satisfiability and solver performance for fixed density random 3-CNF instances, Maximum renamable Horn sub-CNFs, Known and new classes of generalized Horn formulae with polynomial recognition and SAT testing, On the size of maximum renamable Horn sub-CNF, Backdoors to Satisfaction

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The node-deletion problem for hereditary properties is NP-complete
• Detecting embedded Horn structure in propositional logic
• Some simplified NP-complete graph problems
• Recognition of \(q\)-Horn formulae in linear time
• Polynomial-time inference of all valid implications for Horn and related formulae
• Algorithms for testing the satisfiability of propositional formulae
• Renaming a Set of Clauses as a Horn Set
• A Complexity Index for Satisfiability Problems
• Node-and edge-deletion NP-complete problems