Exclusive and essential sets of implicates of Boolean functions

DOI10.1016/j.dam.2009.08.012zbMath1194.06010OpenAlexW2108552370WikidataQ59560551 ScholiaQ59560551MaRDI QIDQ968115

Petr Kučera, Endre Boros, Ondřej Čepek, Alexander 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

Horn functionBoolean minimizationessential setexclusive set

Mathematics Subject Classification ID

Boolean functions (06E30)

Related Items

Learning a propagation complete formula ⋮ A decomposition method for CNF minimality proofs ⋮ Boolean functions with a simple certificate for CNF complexity ⋮ Boolean functions with long prime implicants ⋮ Hardness results for approximate pure Horn CNF formulae minimization ⋮ A subclass of Horn CNFs optimally compressible in polynomial time ⋮ On implicational bases of closure systems with unique critical sets. ⋮ Disjoint essential sets of implicates of a CQ Horn function

Cites Work

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