Hierarchies of polynomially solvable satisfiability problems

DOI10.1007/BF02127974zbMATH Open0891.68108MaRDI QIDQ1380432FDOQ1380432

Authors: D. Pretolani 

Publication date: 19 July 1998

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

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

zbMATH Keywords

propositional satisfiability problem

Mathematics Subject Classification ID

Knowledge representation (68T30)

Cites Work

• Polynomial-time inference of all valid implications for Horn and related formulae
• Title not available (Why is that?)
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• A hierarchy of tractable satisfiability problems
• On-line algorithms for polynomially solvable satisfiability problems
• Extended Horn sets in propositional logic
• On renamable Horn and generalized Horn functions
• Polynomially solvable satisfiability problems
• The satisfiabilty problem for a class consisting of horn sentences and some non-horn sentences in proportional logic
• On generalized Horn formulas and \(k\)-resolution
• Recognizing renamable generalized propositional Horn formulas is NP- complete

Cited In (15)

• A hierarchy of tractable satisfiability problems
• PURL: a new polynomial-time solvable class of satisfiability
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Recognition of tractable satisfiability problems through balanced polynomial representations
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)