A CNF Class Generalizing Exact Linear Formulas
From MaRDI portal
Publication:3502711
DOI10.1007/978-3-540-79719-7_22zbMath1138.68550MaRDI QIDQ3502711
Stefan Porschen, Ewald Speckenmeyer
Publication date: 27 May 2008
Published in: Theory and Applications of Satisfiability Testing – SAT 2008 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-79719-7_22
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
03B05: Classical propositional logic
Related Items
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Nested satisfiability
- On finding solutions for extended Horn formulas
- A simplified NP-complete satisfiability problem
- Satisfiability of mixed Horn formulas
- Solving satisfiability in less than \(2^ n\) steps
- LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Recognition of \(q\)-Horn formulae in linear time
- Polynomial-time inference of all valid implications for Horn and related formulae
- A perspective on certain polynomial-time solvable classes of satisfiability
- One More Occurrence of Variables Makes Satisfiability Jump from Trivial to NP-Complete
- Renaming a Set of Clauses as a Horn Set
- A CNF Formula Hierarchy over the Hypercube
- The complexity of satisfiability problems
- On Linear CNF Formulas