Hierarchies of polynomially solvable satisfiability problems

DOI10.1007/BF02127974MaRDI QIDQ1380432zbMATH OpenFDO

Authors D. Pretolani

Publication date 19 July 1998

Published in Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

zbMATH Keywords

propositional satisfiability problem

Mathematics Subject Classification ID

Knowledge representation (68T30)

Recommendations

• A hierarchy of tractable satisfiability problems
• Polynomially solvable satisfiability problems
• Known and new classes of generalized Horn formulae with polynomial recognition and SAT testing
• A perspective on certain polynomial-time solvable classes of satisfiability

Cites work

• scientific article; zbMATH DE number 3568056 (Why is no real title available?)
• A hierarchy of tractable satisfiability problems
• Extended Horn sets in propositional logic
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• On generalized Horn formulas and k-resolution
• On renamable Horn and generalized Horn functions
• On-line algorithms for polynomially solvable satisfiability problems
• Polynomial-time inference of all valid implications for Horn and related formulae
• Polynomially solvable satisfiability problems
• 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

Cited in

(15)

• A hierarchy of tractable satisfiability problems
• PURL: a new polynomial-time solvable class of satisfiability
• scientific article; zbMATH DE number 751134 (Why is no real title available?)
• Polynomially solvable satisfiability problems
• A perspective on certain polynomial-time solvable classes of satisfiability
• On some tractable classes in deduction and abduction
• A hierarchy of propositional Horn formuls
• Known and new classes of generalized Horn formulae with polynomial recognition and SAT testing
• On functional dependencies in q-Horn theories
• On the complexity of inconsistency measurement
• scientific article; zbMATH DE number 2127871 (Why is no real title available?)
• Recognition of tractable satisfiability problems through balanced polynomial representations
• scientific article; zbMATH DE number 5499325 (Why is no real title available?)
• scientific article; zbMATH DE number 17806 (Why is no real title available?)
• Proper hierarchies in polylogarithmic time and absence of complete problems

This page was built for publication: Hierarchies of polynomially solvable satisfiability problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1380432)