Unique satisfiability of Horn sets can be solved in nearly linear time
From MaRDI portal
Publication:1894352
DOI10.1016/0166-218X(94)00043-DzbMath0836.68054MaRDI QIDQ1894352
Kenneth A. Berman, John S. Schlipf, John V. Franco
Publication date: 6 September 1995
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
03D20: Recursive functions and relations, subrecursive hierarchies
Related Items
A linear time algorithm for unique Horn satisfiability, Fast algorithms for revision of some special propositional knowledge bases, Sorting, linear time and the satisfiability problem
Cites Work
- Unnamed Item
- Unnamed Item
- The unique Horn-satisfiability problem and quadratic Boolean equations.
- On the unique satisfiability problem
- A note on Dowling and Gallier's top-down algorithm for propositional Horn satisfiability
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- Unification as a complexity measure for logic programming
- Efficiency of a Good But Not Linear Set Union Algorithm
- The Semantics of Predicate Logic as a Programming Language
- Depth-First Search and Linear Graph Algorithms