The unique Horn-satisfiability problem and quadratic Boolean equations.

DOI10.1007/BF01531031MaRDI QIDQ1353999zbMATH OpenOpenAlexFDO

Authors 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

Recommendations

• A linear time algorithm for unique Horn satisfiability
• Unique satisfiability of Horn sets can be solved in nearly linear time
• Uniquely solvable quadratic Boolean equations
• Unique Horn renaming and Unique 2-Satisfiability

Cites work

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

Cited in

(8)

• A linear time algorithm for unique Horn satisfiability
• Uniquely solvable quadratic Boolean equations
• Fast algorithms for revision of some special propositional knowledge bases
• A new algorithm for the propositional satisfiability problem
• Unique satisfiability of Horn sets can be solved in nearly linear time
• Recognition of q-Horn formulae in linear time
• On functional dependencies in q-Horn theories
• Unique Horn renaming and Unique 2-Satisfiability

Describes a project that uses

Uses Software

• Ltur

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

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