Recognizing renamable generalized propositional Horn formulas is NP-complete
Authors:
- 21 April 1995
- journal article
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 59 (1) , 23-31
Abstract
No abstract availableKeywords
This publication has 9 references indexed in Scilit:
- Detecting embedded Horn structure in propositional logicInformation Processing Letters, 1992
- Extended Horn sets in propositional logicJournal of the ACM, 1991
- On renamable Horn and generalized Horn functionsAnnals of Mathematics and Artificial Intelligence, 1990
- Polynomially solvable satisfiability problemsInformation Processing Letters, 1988
- LTUR: a simplified linear-time unit resolution algorithm for horn formulae and computer implementationInformation Processing Letters, 1988
- Linear-time algorithms for testing the satisfiability of propositional horn formulaeThe Journal of Logic Programming, 1984
- The satisfiabilty problem for a class consisting of horn sentences and some non-horn sentences in proportional logicInformation and Control, 1983
- Recognizing disguised NR(1) instances of the satisfiability problemJournal of Algorithms, 1980
- Renaming a Set of Clauses as a Horn SetJournal of the ACM, 1978