Hierarchies of polynomially solvable satisfiability problems
From MaRDI portal
Publication:1380432
DOI10.1007/BF02127974zbMath0891.68108MaRDI QIDQ1380432
Publication date: 19 July 1998
Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)
Related Items (3)
On some tractable classes in deduction and abduction ⋮ On the complexity of inconsistency measurement ⋮ On functional dependencies in \(q\)-Horn theories
Cites Work
- Unnamed Item
- On generalized Horn formulas and \(k\)-resolution
- Polynomially solvable satisfiability problems
- A hierarchy of tractable satisfiability problems
- Polynomial-time inference of all valid implications for Horn and related formulae
- On renamable Horn and generalized Horn functions
- Recognizing renamable generalized propositional Horn formulas is NP- complete
- The satisfiabilty problem for a class consisting of horn sentences and some non-horn sentences in proportional logic
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- On-line algorithms for polynomially solvable satisfiability problems
- Extended Horn sets in propositional logic
This page was built for publication: Hierarchies of polynomially solvable satisfiability problems
