Recognizing renamable generalized propositional Horn formulas is NP- complete
From MaRDI portal
Publication:1804878
DOI10.1016/0166-218X(93)E0152-OzbMATH Open0822.68050MaRDI QIDQ1804878FDOQ1804878
Authors: Thomas Eiter, Pekka Kilpeläinen, Heikki Mannila 
Publication date: 17 May 1995
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Recommendations
Cites Work
- LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation
- Title not available (Why is that?)
- Title not available (Why is that?)
- Renaming a Set of Clauses as a Horn Set
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- Detecting embedded Horn structure in propositional logic
- Recognizing disguised NR(1) instances of the satisfiability problem
- Extended Horn sets in propositional logic
- On renamable Horn and generalized Horn functions
- Polynomially solvable satisfiability problems
- The satisfiabilty problem for a class consisting of horn sentences and some non-horn sentences in proportional logic
Cited In (8)
- Recognition of simple enlarged Horn formulas and simple extended Horn formulas
- On some tractable classes in deduction and abduction
- Known and new classes of generalized Horn formulae with polynomial recognition and SAT testing
- Detecting embedded Horn structure in propositional logic
- Complexities of renaming for formulas in MAX(1) and MARG(1)
- Hierarchies of polynomially solvable satisfiability problems
- Investigations on autark assignments
- The complexity of renamings for formulas in MAX and MARG
This page was built for publication: Recognizing renamable generalized propositional Horn formulas is NP- complete
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1804878)
