Recognizing renamable generalized propositional Horn formulas is NP- complete

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)

zbMATH Keywords

NP-completenessHorn formulassatisfiability problem

Mathematics Subject Classification ID

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

Recommendations

• On renamable Horn and generalized Horn functions
• Existence of simple propositional formulas
• The complexity of renamings for formulas in MAX and MARG
• scientific article; zbMATH DE number 3892614
• Complexities of renaming for formulas in MAX(1) and MARG(1)

Cites work

• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Detecting embedded Horn structure in propositional logic
• Extended Horn sets in propositional logic
• LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• On renamable Horn and generalized Horn functions
• Polynomially solvable satisfiability problems
• Recognizing disguised NR(1) instances of the satisfiability problem
• Renaming a Set of Clauses as a Horn Set
• The satisfiabilty problem for a class consisting of horn sentences and some non-horn sentences in proportional logic

Cited in

(8)

• Known and new classes of generalized Horn formulae with polynomial recognition and SAT testing
• On some tractable classes in deduction and abduction
• Hierarchies of polynomially solvable satisfiability problems
• Recognition of simple enlarged Horn formulas and simple extended Horn formulas
• The complexity of renamings for formulas in MAX and MARG
• Investigations on autark assignments
• Complexities of renaming for formulas in MAX(1) and MARG(1)
• Detecting embedded Horn structure in propositional logic

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)