Variable and term removal from Boolean formulae
From MaRDI portal
Publication:1363769
DOI10.1016/S0166-218X(96)00028-5zbMATH Open0879.94041OpenAlexW1983342871MaRDI QIDQ1363769FDOQ1363769
Authors: Oya Ekin, Yves Crama, Peter L. Hammer 
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
Recommendations
Cites Work
- Title not available (Why is that?)
- The node-deletion problem for hereditary properties is NP-complete
- Recognition of \(q\)-Horn formulae in linear time
- Polynomial-time inference of all valid implications for Horn and related formulae
- Title not available (Why is that?)
- Renaming a Set of Clauses as a Horn Set
- Some simplified NP-complete graph problems
- Node-and edge-deletion NP-complete problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Detecting embedded Horn structure in propositional logic
- Algorithms for testing the satisfiability of propositional formulae
- A Complexity Index for Satisfiability Problems
- Title not available (Why is that?)
Cited In (11)
- Disjoint DNF tautologies with conflict bound two
- Backdoors to q-Horn
- Backdoor DNFs
- Backdoors to planning
- Known and new classes of generalized Horn formulae with polynomial recognition and SAT testing
- Maximum renamable Horn sub-CNFs
- Backdoors into Two Occurrences
- Backdoor sets of quantified Boolean formulas
- Correlations between Horn fractions, satisfiability and solver performance for fixed density random 3-CNF instances
- On the size of maximum renamable Horn sub-CNF
- Backdoors to Satisfaction
This page was built for publication: Variable and term removal from Boolean formulae
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1363769)
