A subclass of Horn CNFs optimally compressible in polynomial time

DOI10.1007/s10472-010-9197-7zbMath1253.68311OpenAlexW1999427653WikidataQ59560576 ScholiaQ59560576MaRDI QIDQ693287

Endre Boros, Petr Kučera, Alexander Kogan, Ondřej Čepek

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)

Related Items (10)

Optimum basis of finite convex geometry ⋮ A decomposition method for CNF minimality proofs ⋮ Properties of Switch-List Representations of Boolean Functions ⋮ Boolean functions with long prime implicants ⋮ The joy of implications, aka pure Horn formulas: mainly a survey ⋮ Recognition of tractable DNFs representable by a constant number of intervals ⋮ Translating between the representations of a ranked convex geometry ⋮ Dualization in lattices given by implicational bases ⋮ Disjoint essential sets of implicates of a CQ Horn function ⋮ Approximating Minimum Representations of Key Horn Functions

Uses Software

• Ltur

Cites Work

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

This page was built for publication: A subclass of Horn CNFs optimally compressible in polynomial time