Detecting embedded Horn structure in propositional logic

DOI10.1016/0020-0190(92)90098-GMaRDI QIDQ1198035zbMATH OpenOpenAlexFDO

Authors S. Singh

Publication date 16 January 1993

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(92)90098-g

zbMATH Keywords

maximum clique problemmaximum renamable Horn problemNP-hardpropositional satisfiability problemset packing problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in artificial intelligence (68T27)

Recommendations

• Maximum renamable Horn sub-CNFs
• Recognizing renamable generalized propositional Horn formulas is NP- complete
• On renamable Horn and generalized Horn functions
• Extended Horn sets in propositional logic
• On the complexity of the maximum satisfiability problem for Horn formulas

Cites work

• An exact algorithm for the maximum clique problem
• Computational aspects of a branch and bound algorithm for quadratic zero- one programming
• Finding a Maximum Clique in an Arbitrary Graph
• scientific article; zbMATH DE number 4064507 (Why is no real title available?)
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• On renamable Horn and generalized Horn functions
• Recognizing disguised NR(1) instances of the satisfiability problem

Cited in

(7)

• Variable and term removal from Boolean formulae
• Recognizing renamable generalized propositional Horn formulas is NP- complete
• Testing heuristics: We have it all wrong
• Maximum renamable Horn sub-CNFs
• Mixed logical-linear programming
• Tradeoffs in the Complexity of Backdoor Detection
• Tradeoffs in the complexity of backdoors to satisfiability: dynamic sub-solvers and learning during search

This page was built for publication: Detecting embedded Horn structure in propositional logic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1198035)