An \(O(n^ 2)\) algorithm for the satisfiability problem of a subset of propositional sentences in CNF that includes all Horn sentences (Q1097717): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
| Property / cites work | |||
| Property / cites work: Unification as a complexity measure for logic programming / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: The satisfiabilty problem for a class consisting of horn sentences and some non-horn sentences in proportional logic / rank | |||
Normal rank | |||
Latest revision as of 14:41, 18 June 2024
scientific article
| 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 |
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
