Recognition of q-Horn formulae in linear time
Authors:
- Endre BorosEBEndre Boros
- Peter L. HammerPHPeter L. Hammer
- Xiaorong SunXSXiaorong Sun
- 1 October 1994
- journal article
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 55 (1) , 1-13
Abstract
No abstract availableKeywords
This publication has 15 references indexed in Scilit:
- A Complexity Index for Satisfiability ProblemsSIAM Journal on Computing, 1994
- Extended Horn sets in propositional logicJournal of the ACM, 1991
- Algorithms for testing the satisfiability of propositional formulaeThe Journal of Logic Programming, 1989
- Linear-time algorithms for testing the satisfiability of propositional horn formulaeThe Journal of Logic Programming, 1984
- A simplified NP-complete satisfiability problemDiscrete Applied Mathematics, 1984
- Recognizing disguised NR(1) instances of the satisfiability problemJournal of Algorithms, 1980
- A linear-time algorithm for testing the truth of certain quantified boolean formulasInformation Processing Letters, 1979
- Renaming a Set of Clauses as a Horn SetJournal of the ACM, 1978
- On the Complexity of Timetable and Multicommodity Flow ProblemsSIAM Journal on Computing, 1976
- Complete problems for deterministic polynomial timeTheoretical Computer Science, 1976