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

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)

zbMATH Keywords

Horn clausesHorn set

Mathematics Subject Classification ID

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

Related Items (3)

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