An \(O(n^ 2)\) algorithm for the satisfiability problem of a subset of propositional sentences in CNF that includes all Horn sentences (Q1097717)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: An \(O(n^ 2)\) algorithm for the satisfiability problem of a subset of propositional sentences in CNF that includes all Horn sentences |
scientific article; zbMATH DE number 4035207
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | An \(O(n^ 2)\) algorithm for the satisfiability problem of a subset of propositional sentences in CNF that includes all Horn sentences |
scientific article; zbMATH DE number 4035207 |
Statements
An \(O(n^ 2)\) algorithm for the satisfiability problem of a subset of propositional sentences in CNF that includes all Horn sentences (English)
0 references
1987
0 references
Based on the results of Ìtai and Makowsky that recognize satisfiable Horn sentences in O(n) time, the authors present in this paper an algorithm that improves the performance of the algorithm of Yamasaki and Doshita of solving the satisfiability problem for a class \(S_ 0\) of propositional sentences that properly contains all Horn sentences. The algorithm, its correctness and complexity, and the structure of \(S_ 0\) are presented.
0 references
Horn sentences
0 references
satisfiability problem
0 references
propositional sentences
0 references
complexity
0 references
