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)

Full work available at URL https://doi.org/10.1007/BF02127974

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

• A hierarchy of tractable satisfiability problems
• Extended Horn sets in propositional logic
• scientific article; zbMATH DE number 3568056 (Why is no real title available?)
• 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

(16)

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

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)