On Approximate Horn Formula Minimization
From MaRDI portal
Publication:3587398
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
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