Approximating Minimum Representations of Key Horn Functions

DOI10.1137/19M1275681zbMath1504.68052arXiv1811.05160OpenAlexW2901129014MaRDI QIDQ5863327

Endre Boros, Kristóf Bérczi, Kazuhisa Makino, Petr Kučera, Ondřej Čepek

Publication date: 11 March 2022

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1811.05160

zbMATH Keywords

approximation algorithmsdirected hypergraphsHorn minimizationimplicational systems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Database theory (68P15) Hypergraphs (05C65) Classical propositional logic (03B05) Boolean functions (06E30) Approximation algorithms (68W25)

Related Items (2)

Unique key Horn functions ⋮ Matroid Horn functions

Uses Software

• JBool

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A decomposition method for CNF minimality proofs
• Hydras: complexity on general graphs and a subclass of trees
• Hydras: directed hypergraphs and Horn formulas
• The complexity of Boolean formula minimization
• A subclass of Horn CNFs optimally compressible in polynomial time
• A simplified NP-complete satisfiability problem
• Structure identification in relational data
• Horn minimization by iterative decomposition
• Optimal compression of propositional Horn knowledge bases: Complexity and approximation
• The minimum equivalent DNF problem and shortest implicants
• The lattices of closure systems, closure operators, and implicational systems on a finite set: A survey
• On strongly connected digraphs with bounded cycle length
• Hardness results for approximate pure Horn CNF formulae minimization
• On Approximate Horn Formula Minimization
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• Minimal Representation of Directed Hypergraphs
• Approximation Algorithms for Several Graph Augmentation Problems
• Minimum Covers in Relational Database Model
• Optimum branchings
• The Transitive Reduction of a Directed Graph
• The complexity of theorem-proving procedures

This page was built for publication: Approximating Minimum Representations of Key Horn Functions