On Approximate Horn Formula Minimization

DOI10.1007/978-3-642-14165-2_38zbMath1288.68086OpenAlexW1593671397MaRDI QIDQ3587398

György Turán, Dhruv Mubayi, Amitava Bhattacharya, Bhaskar Das Gupta

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)

Related Items (8)

Directed hypergraphs and Horn minimization ⋮ A decomposition method for CNF minimality proofs ⋮ The algebraic structure of the densification and the sparsification tasks for CSPs ⋮ Hydras: complexity on general graphs and a subclass of trees ⋮ Hydras: directed hypergraphs and Horn formulas ⋮ Hardness results for approximate pure Horn CNF formulae minimization ⋮ On the hydra number of disconnected graphs ⋮ Approximating Minimum Representations of Key Horn Functions

This page was built for publication: On Approximate Horn Formula Minimization