Boolean functions with long prime implicants

DOI10.1016/J.IPL.2013.07.001MaRDI QIDQ2445231zbMATH OpenOpenAlexWikidataFDO

Authors Ondřej Čepek, Petr Kučera, Stanislav Kuřík

Publication date 14 April 2014

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2013.07.001

zbMATH Keywords

analysis of algorithmsapproximation algorithmsBoolean minimizationconsensus methodDNFset cover

Mathematics Subject Classification ID

Boolean functions (06E30) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Recommendations

• The minimum equivalent DNF problem and shortest implicants
• A minimization method for boolean functions
• Boolean functions with a simple certificate for CNF complexity
• scientific article; zbMATH DE number 3974901
• Publication:4938653

Cites work

• A subclass of Horn CNFs optimally compressible in polynomial time
• A Way to Simplify Truth Functions
• An Algorithm for a Minimum Cover of a Graph
• Analysis of approximation algorithms for k-set cover using factor-revealing linear programs
• Approximating the Unweighted k-Set Cover Problem: Greedy Meets Local Search
• Exclusive and essential sets of implicates of Boolean functions
• Horn minimization by iterative decomposition
• scientific article; zbMATH DE number 5852793 (Why is no real title available?)
• scientific article; zbMATH DE number 4053069 (Why is no real title available?)
• scientific article; zbMATH DE number 3758364 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1470716 (Why is no real title available?)
• scientific article; zbMATH DE number 1559541 (Why is no real title available?)
• Isoperimetric inequalities for faces of the cube and the grid
• Minimal Representation of Directed Hypergraphs
• Minimum Covers in Relational Database Model
• Optimal compression of propositional Horn knowledge bases: Complexity and approximation
• The complexity of theorem-proving procedures
• The minimum equivalent DNF problem and shortest implicants

Cited in

(5)

• The minimum equivalent DNF problem and shortest implicants
• Monotone Boolean functions capture their primes
• scientific article; zbMATH DE number 1405672 (Why is no real title available?)
• A Numerical Procedure for Determination of the Prime Implicants of a Boolean Function
• Title not available (Why is no real title available?)

Describes a project that uses

Uses Software

• JBool

This page was built for publication: Boolean functions with long prime implicants

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