A linear time algorithm for unique Horn satisfiability (Q1313762): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 12:56, 31 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A linear time algorithm for unique Horn satisfiability |
scientific article |
Statements
A linear time algorithm for unique Horn satisfiability (English)
0 references
24 February 1994
0 references
The Unique-HornSAT problem asks whether there exists a unique solution to a given Horn satisfiability problem. Here, we propose a linear time Unique-HornSAT algorithm. We use directed hypergraphs to represent Horn formulas; our method combines a hypergraph transformation technique with the search of strongly connected components in a sub-graph. In the proposed implementation, we solve a particular disjoint set union problem, for which linear amortized time algorithms are known. A similar result was obtained independently by Berman, Franco and Schlipf, although they fail to obtain a linear complexity.
0 references
satisfiability
0 references
directed hypergraphs
0 references
Horn formulas
0 references
disjoint set union
0 references