Recognizing renamable generalized propositional Horn formulas is NP- complete

DOI10.1016/0166-218X(93)E0152-OzbMath0822.68050MaRDI QIDQ1804878

Thomas Eiter, Pekka Kilpeläinen, Heikki Mannila

Publication date: 17 May 1995

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

NP-completenesssatisfiability problemHorn formulas

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Classical propositional logic (03B05)

Related Items (4)

Known and new classes of generalized Horn formulae with polynomial recognition and SAT testing ⋮ Hierarchies of polynomially solvable satisfiability problems ⋮ On some tractable classes in deduction and abduction ⋮ Investigations on autark assignments

Cites Work

• Unnamed Item
• Unnamed Item
• LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation
• Polynomially solvable satisfiability problems
• Detecting embedded Horn structure in propositional logic
• On renamable Horn and generalized Horn functions
• The satisfiabilty problem for a class consisting of horn sentences and some non-horn sentences in proportional logic
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• Recognizing disguised NR(1) instances of the satisfiability problem
• Renaming a Set of Clauses as a Horn Set
• Extended Horn sets in propositional logic

This page was built for publication: Recognizing renamable generalized propositional Horn formulas is NP- complete