Exclusive and essential sets of implicates of Boolean functions

DOI10.1016/J.DAM.2009.08.012MaRDI QIDQ968115zbMATH OpenOpenAlexWikidataFDO

Authors Endre Boros, Ondřej Čepek, Alex Kogan, Petr Kučera

Publication date 5 May 2010

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2009.08.012

zbMATH Keywords

Boolean minimizationHorn functionessential setexclusive set

Mathematics Subject Classification ID

Boolean functions (06E30)

Recommendations

• Disjoint essential sets of implicates of a CQ Horn function
• Boolean functions with a simple certificate for CNF complexity
• Disjunctive and conjunctive normal forms of pseudo-Boolean functions
• On the weights of Boolean functions representable by 2-CNF or 3-CNF
• On the gap between \(\mathit{ess}(f)\) and \(\mathit{cnf}_{-}\mathit{size}(f)\)

Cites work

• scientific article; zbMATH DE number 4053069 (Why is no real title available?)
• scientific article; zbMATH DE number 3566230 (Why is no real title available?)
• scientific article; zbMATH DE number 1470716 (Why is no real title available?)
• A Way to Simplify Truth Functions
• Decomposition of a Data Base and the Theory of Boolean Switching Functions
• Depth-First Search and Linear Graph Algorithms
• Horn functions and their DNFs
• Horn minimization by iterative decomposition
• Minimal Representation of Directed Hypergraphs
• Minimum Covers in Relational Database Model
• Optimal compression of propositional Horn knowledge bases: Complexity and approximation
• The Problem of Simplifying Truth Functions
• The minimum equivalent DNF problem and shortest implicants

Cited in

(12)

• Hardness results for approximate pure Horn CNF formulae minimization
• A decomposition method for CNF minimality proofs
• Boolean functions with long prime implicants
• On the gap between \(\mathit{ess}(f)\) and \(\mathit{cnf}_{-}\mathit{size}(f)\)
• Disjoint essential sets of implicates of a CQ Horn function
• A subclass of Horn CNFs optimally compressible in polynomial time
• Boolean functions with a simple certificate for CNF complexity
• On implicational bases of closure systems with unique critical sets.
• scientific article; zbMATH DE number 1740046 (Why is no real title available?)
• scientific article; zbMATH DE number 1134609 (Why is no real title available?)
• The ghosts of forgotten things: a study on size after forgetting
• Learning a propagation complete formula

This page was built for publication: Exclusive and essential sets of implicates of Boolean functions

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