A subclass of Horn CNFs optimally compressible in polynomial time

DOI10.1007/S10472-010-9197-7MaRDI QIDQ693287zbMATH OpenOpenAlexDBLPWikidataFDO

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

zbMATH Keywords

Boolean minimizationHorn minimizationessential setsCQ functionsexclusive setsHorn functionspolynomial-time HM algorithmpropositional Horn expert systems

Mathematics Subject Classification ID

Theory of languages and software systems (knowledge-based systems, expert systems, etc.) for artificial intelligence (68T35) Boolean functions (06E30)

Recommendations

• Horn minimization by iterative decomposition
• Optimal compression of propositional Horn knowledge bases: Complexity and approximation
• Directed hypergraphs and Horn minimization
• Horn functions and their DNFs
• Hardness results for approximate pure Horn CNF formulae minimization

Cites work

• scientific article; zbMATH DE number 4053069 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1946853 (Why is no real title available?)
• A Way to Simplify Truth Functions
• Augmentation Problems
• Decomposition of a Data Base and the Theory of Boolean Switching Functions
• Depth-First Search and Linear Graph Algorithms
• Exclusive and essential sets of implicates of Boolean functions
• Functional dependencies in Horn theories
• Horn functions and their DNFs
• Horn minimization by iterative decomposition
• Knowledge compilation and theory approximation
• LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• Minimal Representation of Directed Hypergraphs
• Minimum Covers in Relational Database Model
• On functional dependencies in \(q\)-Horn theories
• Optimal compression of propositional Horn knowledge bases: Complexity and approximation
• Structure identification in relational data
• The Problem of Simplifying Truth Functions
• Unification as a complexity measure for logic programming

Cited in

(12)

• Hardness results for approximate pure Horn CNF formulae minimization
• A decomposition method for CNF minimality proofs
• Boolean functions with long prime implicants
• Approximating minimum representations of key Horn functions
• Optimum basis of finite convex geometry
• Translating between the representations of a ranked convex geometry
• Disjoint essential sets of implicates of a CQ Horn function
• Optimal compression of propositional Horn knowledge bases: Complexity and approximation
• Recognition of tractable DNFs representable by a constant number of intervals
• The joy of implications, aka pure Horn formulas: mainly a survey
• Properties of Switch-List Representations of Boolean Functions
• scientific article; zbMATH DE number 4085615 (Why is no real title available?)

Describes a project that uses

Uses Software

• Ltur

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)