Unique satisfiability of Horn sets can be solved in nearly linear time

DOI10.1016/0166-218X(94)00043-DMaRDI QIDQ1894352zbMATH OpenFDO

Authors Kenneth A. Berman, John S. Schlipf, John V. Franco

Publication date 6 September 1995

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218X(94)00043-D

zbMATH Keywords

Horn clausesHorn set

Mathematics Subject Classification ID

Recursive functions and relations, subrecursive hierarchies (03D20) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A linear time algorithm for unique Horn satisfiability
• LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation
• The unique Horn-satisfiability problem and quadratic Boolean equations.
• Unique Horn renaming and Unique 2-Satisfiability
• Linear-time algorithms for testing the satisfiability of propositional horn formulae

Cites work

• A note on Dowling and Gallier's top-down algorithm for propositional Horn satisfiability
• Depth-First Search and Linear Graph Algorithms
• Efficiency of a Good But Not Linear Set Union Algorithm
• scientific article; zbMATH DE number 3481857 (Why is no real title available?)
• scientific article; zbMATH DE number 3566230 (Why is no real title available?)
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• On the unique satisfiability problem
• The Semantics of Predicate Logic as a Programming Language
• The unique Horn-satisfiability problem and quadratic Boolean equations.
• Unification as a complexity measure for logic programming

Cited in

(5)

• A linear time algorithm for unique Horn satisfiability
• The unique Horn-satisfiability problem and quadratic Boolean equations.
• Fast algorithms for revision of some special propositional knowledge bases
• Sorting, linear time and the satisfiability problem
• Unique Horn renaming and Unique 2-Satisfiability

This page was built for publication: Unique satisfiability of Horn sets can be solved in nearly linear time

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