A note on Dowling and Gallier's top-down algorithm for propositional Horn satisfiability
From MaRDI portal
DOI10.1016/0743-1066(90)90026-2zbMATH Open0705.68091OpenAlexW2061917453MaRDI QIDQ3485885FDOQ3485885
Authors: Maria Grazia Scutellà 
Publication date: 1990
Published in: The Journal of Logic Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0743-1066(90)90026-2
Recommendations
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- Algorithms for testing the satisfiability of propositional formulae
- LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation
- An \(O(n^ 2)\) algorithm for the satisfiability problem of a subset of propositional sentences in CNF that includes all Horn sentences
- scientific article; zbMATH DE number 4085614
Analysis of algorithms and problem complexity (68Q25) Classical propositional logic (03B05) Mechanization of proofs and logical operations (03B35)
Cited In (13)
- A perspective on certain polynomial-time solvable classes of satisfiability
- On exact selection of minimally unsatisfiable subformulae
- Unique satisfiability of Horn sets can be solved in nearly linear time
- A short note on some tractable cases of the satisfiability problem.
- Complexity and undecidability results for logic programming
- Solving the resolution-free SAT problem by submodel propagation in linear time
- Computing the well-founded semantics faster
- Fuzzy logic programs as hypergraphs. Termination results
- Logic programs and connectionist networks
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation
- About some UP-based polynomial fragments of SAT
- A sharp threshold for the renameable-Horn and the \(q\)-Horn properties
This page was built for publication: A note on Dowling and Gallier's top-down algorithm for propositional Horn satisfiability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3485885)
