Horn functions and their DNFs

DOI10.1016/0020-0190(92)90250-YzbMath0794.68148MaRDI QIDQ1195858

Peter L. Hammer, Alexander Kogan

Publication date: 4 January 1993

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

Boolean functions; disjunctive normal forms; knowledge bases; Horn functions

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R05: Combinatorics in computer science

68T27: Logic in artificial intelligence

Related Items

A decomposition method for CNF minimality proofs, Boolean functions with a simple certificate for CNF complexity, Hydras: directed hypergraphs and Horn formulas, A subclass of Horn CNFs optimally compressible in polynomial time, Disjoint essential sets of implicates of a CQ Horn function, Exclusive and essential sets of implicates of Boolean functions, The multiple facets of the canonical direct unit implicational basis, Recognition of interval Boolean functions, Double Horn functions, Optimal compression of propositional Horn knowledge bases: Complexity and approximation, Horn functions and submodular Boolean functions, On functional dependencies in \(q\)-Horn theories, Recognition and dualization of disguised bidual Horn functions., Properties of quasi-Boolean function on quasi-Boolean algebra, Bidual Horn functions and extensions, Hardness results for approximate pure Horn CNF formulae minimization, Generalized domination in closure systems, Horn representation of a concept lattice

Uses Software

• Ltur

Cites Work

• Unnamed Item
• LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation
• Polynomial-time inference of all valid implications for Horn and related formulae
• A Way to Simplify Truth Functions
• Linear-time algorithms for testing the satisfiability of propositional horn formulae