Approximating minimum representations of key Horn functions

DOI10.1137/19M1275681MaRDI QIDQ5863327zbMATH OpenOpenAlexFDO

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

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

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

Abstract: Horn functions form a subclass of Boolean functions and appear in many different areas of computer science and mathematics as a general tool to describe implications and dependencies. Finding minimum sized representations for such functions with respect to most commonly used measures is a computationally hard problem that remains hard even for the important subclass of key Horn functions. In this paper we provide logarithmic factor approximation algorithms for key Horn functions with respect to all measures studied in the literature for which the problem is known to be hard.

Recommendations

• Unique key Horn functions
• A subclass of Horn CNFs optimally compressible in polynomial time
• Horn functions and their DNFs
• Directed hypergraphs and Horn minimization
• Horn minimization by iterative decomposition

Cites work

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

Cited in

(4)

• Horn functions and their DNFs
• Unique key Horn functions
• On approximate Horn formula minimization
• Matroid Horn functions

Describes a project that uses

Uses Software

• JBool

This page was built for publication: Approximating minimum representations of key Horn functions

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