The unique Horn-satisfiability problem and quadratic Boolean equations.

DOI10.1007/BF01531031zbMath1034.68543OpenAlexW1991763698MaRDI QIDQ1353999

Michel Minoux

Publication date: 13 May 1997

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01531031

zbMATH Keywords

Horn expression

Mathematics Subject Classification ID

Related Items (5)

Unique satisfiability of Horn sets can be solved in nearly linear time ⋮ A new algorithm for the propositional satisfiability problem ⋮ Fast algorithms for revision of some special propositional knowledge bases ⋮ A linear time algorithm for unique Horn satisfiability ⋮ On functional dependencies in \(q\)-Horn theories

Uses Software

• Ltur

Cites Work

• The complexity of facets (and some facets of complexity)
• Uniquely solvable quadratic Boolean equations
• LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation
• Complete problems for deterministic polynomial time
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• On the unique satisfiability problem
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• On the complexity of unique solutions
• Note on the Condition that a Boolean Equation Have a Unique Solution

This page was built for publication: The unique Horn-satisfiability problem and quadratic Boolean equations.