A subclass of Horn CNFs optimally compressible in polynomial time
DOI10.1007/S10472-010-9197-7zbMATH Open1253.68311DBLPjournals/amai/BorosCKK09OpenAlexW1999427653WikidataQ59560576 ScholiaQ59560576MaRDI QIDQ693287FDOQ693287
Authors: Endre Boros, Ondřej Čepek, Alex Kogan, Petr Kučera 
Publication date: 7 December 2012
Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10472-010-9197-7
Recommendations
Boolean minimizationHorn minimizationessential setsCQ functionsexclusive setsHorn functionspolynomial-time HM algorithmpropositional Horn expert systems
Theory of languages and software systems (knowledge-based systems, expert systems, etc.) for artificial intelligence (68T35) Boolean functions (06E30)
Cites Work
- LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation
- 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
- Knowledge compilation and theory approximation
- 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
- Augmentation Problems
- Title not available (Why is that?)
- Structure identification in relational data
- Horn functions and their DNFs
- Horn minimization by iterative decomposition
- Optimal compression of propositional Horn knowledge bases: Complexity and approximation
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- Unification as a complexity measure for logic programming
- Exclusive and essential sets of implicates of Boolean functions
- Functional dependencies in Horn theories
- On functional dependencies in \(q\)-Horn theories
Cited In (13)
- A decomposition method for CNF minimality proofs
- Dualization in lattices given by implicational bases
- Optimal compression of propositional Horn knowledge bases: Complexity and approximation
- Approximating Minimum Representations of Key Horn Functions
- Title not available (Why is that?)
- Optimum basis of finite convex geometry
- Hardness results for approximate pure Horn CNF formulae minimization
- Boolean functions with long prime implicants
- Translating between the representations of a ranked convex geometry
- Disjoint essential sets of implicates of a CQ Horn function
- The joy of implications, aka pure Horn formulas: mainly a survey
- Recognition of tractable DNFs representable by a constant number of intervals
- Properties of Switch-List Representations of Boolean Functions
Uses Software
This page was built for publication: A subclass of Horn CNFs optimally compressible in polynomial time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q693287)
