Exclusive and essential sets of implicates of Boolean functions

DOI10.1016/J.DAM.2009.08.012zbMATH Open1194.06010OpenAlexW2108552370WikidataQ59560551 ScholiaQ59560551MaRDI QIDQ968115FDOQ968115

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

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)

Cites Work

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

Cited In (11)

• A decomposition method for CNF minimality proofs
• The ghosts of forgotten things: a study on size after forgetting
• A subclass of Horn CNFs optimally compressible in polynomial time
• Title not available (Why is that?)
• Boolean functions with a simple certificate for CNF complexity
• Hardness results for approximate pure Horn CNF formulae minimization
• Boolean functions with long prime implicants
• Learning a propagation complete formula
• Disjoint essential sets of implicates of a CQ Horn function
• Title not available (Why is that?)
• On implicational bases of closure systems with unique critical sets.

   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 👍 👎
• О весах булевых функций, представимых в виде $2$-КНФ или $3$-КНФ 👍 👎
• On the gap between \(\mathit{ess}(f)\) and \(\mathit{cnf}_{-}\mathit{size}(f)\) 👍 👎

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)