Unique Horn renaming and Unique 2-Satisfiability

DOI10.1016/0020-0190(95)00023-6MaRDI QIDQ673674zbMATH OpenOpenAlexFDO

Authors Jean-Jacques Hébrard

Publication date 28 February 1997

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(95)00023-6

zbMATH Keywords

AlgorithmsSatisfiabilityHorn setsRenaming

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10)

Recommendations

• A linear time algorithm for unique Horn satisfiability
• The unique Horn-satisfiability problem and quadratic Boolean equations.
• Unique satisfiability of Horn sets can be solved in nearly linear time
• The complexity of homomorphisms and renamings for minimal unsatisfiable formulas
• On the unique satisfiability problem
• scientific article; zbMATH DE number 8776
• Uniquest: Determining the Semantics of Complex Uniqueness Constraints
• scientific article; zbMATH DE number 3892614
• On renaming a set of clauses as a Horn set
• Satisfiability of mixed Horn formulas

Cites work

• A linear algorithm for renaming a set of clauses as a Horn set
• A linear control algorithm for a class of rule-based systems
• A linear time algorithm for unique Horn satisfiability
• Depth-First Search and Linear Graph Algorithms
• Existence of simple propositional formulas
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• On renamable Horn and generalized Horn functions
• On the unique satisfiability problem
• Recognizing disguised NR(1) instances of the satisfiability problem
• Renaming a Set of Clauses as a Horn Set
• Uniquely solvable quadratic Boolean equations

Cited in

(5)

• A linear time algorithm for unique Horn satisfiability
• On renaming a set of clauses as a Horn set
• Unique satisfiability of Horn sets can be solved in nearly linear time
• Sorting, linear time and the satisfiability problem
• A sharp threshold for the renameable-Horn and the \(q\)-Horn properties

This page was built for publication: Unique Horn renaming and Unique 2-Satisfiability

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