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)
Analysis of algorithms and problem complexity (68Q25) Recursive functions and relations, subrecursive hierarchies (03D20)
Related Items (max. 100)
Fast algorithms for revision of some special propositional knowledge bases ⋮ Sorting, linear time and the satisfiability problem ⋮ A linear time algorithm for unique Horn satisfiability
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
This page was built for publication: Unique satisfiability of Horn sets can be solved in nearly linear time