On approximate Horn formula minimization

DOI10.1007/978-3-642-14165-2_38MaRDI QIDQ3587398zbMATH OpenOpenAlexFDO

Authors Amitava Bhattacharya, Dhruv Mubayi, Gy. Turán, Bhaskar Dasgupta

Publication date 7 September 2010

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-14165-2_38

Mathematics Subject Classification ID

Classical propositional logic (03B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• Hardness results for approximate pure Horn CNF formulae minimization
• Horn minimization by iterative decomposition
• On the Approximability of Splitting-SAT in 2-CNF Horn Formulas
• Strong duality in Horn minimization
• Approximating minimum representations of key Horn functions

Cited in

(9)

• Hardness results for approximate pure Horn CNF formulae minimization
• On the hydra number of disconnected graphs
• Directed hypergraphs and Horn minimization
• A decomposition method for CNF minimality proofs
• Hydras: complexity on general graphs and a subclass of trees
• Hydras: directed hypergraphs and Horn formulas
• Approximating minimum representations of key Horn functions
• The algebraic structure of the densification and the sparsification tasks for CSPs
• Common equivalence and size of forgetting from Horn formulae

This page was built for publication: On approximate Horn formula minimization

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