Variable and term removal from Boolean formulae
From MaRDI portal
Publication:1363769
DOI10.1016/S0166-218X(96)00028-5zbMath0879.94041OpenAlexW1983342871MaRDI QIDQ1363769
Oya Ekin, Peter L. Hammer, Yves Cramer
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
Related Items
Backdoors to Satisfaction ⋮ Known and new classes of generalized Horn formulae with polynomial recognition and SAT testing ⋮ On the size of maximum renamable Horn sub-CNF ⋮ Maximum renamable Horn sub-CNFs ⋮ Correlations between Horn fractions, satisfiability and solver performance for fixed density random 3-CNF instances ⋮ Backdoors to planning ⋮ Backdoor sets of quantified Boolean formulas ⋮ Backdoors into Two Occurrences ⋮ Backdoors to q-Horn
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