Recognition of tractable DNFs representable by a constant number of intervals

DOI10.1016/j.disopt.2016.11.002zbMath1387.68132OpenAlexW2561407776MaRDI QIDQ1751204

Radek Hušek, Ondřej Čepek

Publication date: 24 May 2018

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2016.11.002

zbMATH Keywords

disjunctive normal formsknowledge compilationinterval Boolean functions

Mathematics Subject Classification ID

Related Items (2)

No Efficient Disjunction or Conjunction of Switch-Lists ⋮ Properties of Switch-List Representations of Boolean Functions

Cites Work

• Unnamed Item
• A decomposition method for CNF minimality proofs
• Boolean functions with a simple certificate for CNF complexity
• A subclass of Horn CNFs optimally compressible in polynomial time
• Recognition of interval Boolean functions
• Horn minimization by iterative decomposition
• Optimal compression of propositional Horn knowledge bases: Complexity and approximation
• The minimum equivalent DNF problem and shortest implicants
• Computing the minimum DNF representation of Boolean functions defined by intervals
• Minimal Representation of Directed Hypergraphs

This page was built for publication: Recognition of tractable DNFs representable by a constant number of intervals