A short note on some tractable cases of the satisfiability problem.
From MaRDI portal
Publication:1854345
DOI10.1006/inco.2000.2867zbMath1046.68542OpenAlexW2060398342MaRDI QIDQ1854345
Publication date: 14 January 2003
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/inco.2000.2867
Related Items (8)
Generalising and Unifying SLUR and Unit-Refutation Completeness ⋮ Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets ⋮ Autark assignments of Horn CNFs ⋮ On exact selection of minimally unsatisfiable subformulae ⋮ The Horn renamability, q-Horn and SLUR threshold for random \(k\)-CNF formulas ⋮ A perspective on certain polynomial-time solvable classes of satisfiability ⋮ On functional dependencies in \(q\)-Horn theories ⋮ Generalising unit-refutation completeness and SLUR via nested input resolution
Cites Work
- Unnamed Item
- On finding solutions for extended Horn formulas
- Solving satisfiability in less than \(2^ n\) steps
- Alpha-balanced graphs and matrices and GF(3)-representability of matroids
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Recognition of \(q\)-Horn formulae in linear time
- Investigations on autark assignments
- Solving satisfiability problems using elliptic approximations -- effective branching rules
- A note on Dowling and Gallier's top-down algorithm for propositional Horn satisfiability
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- Renaming a Set of Clauses as a Horn Set
- A Complexity Index for Satisfiability Problems
- Extended Horn sets in propositional logic
- A class of logic problems solvable by linear programming
This page was built for publication: A short note on some tractable cases of the satisfiability problem.
