Boolean functions with a simple certificate for CNF complexity
From MaRDI portal
Publication:412324
DOI10.1016/j.dam.2011.05.013zbMath1246.94056WikidataQ62044326 ScholiaQ62044326MaRDI QIDQ412324
Petr Kučera, Petr Savický, Ondřej Čepek
Publication date: 4 May 2012
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2011.05.013
Related Items
Disjoint essential sets of implicates of a CQ Horn function, Recognition of tractable DNFs representable by a constant number of intervals
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A new polynomial-time algorithm for linear programming
- Exclusive and essential sets of implicates of Boolean functions
- Horn functions and their DNFs
- 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
- The complexity of theorem-proving procedures
- The Problem of Simplifying Truth Functions