Horn functions and their DNFs
From MaRDI portal
Publication:1195858
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)
Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Logic in artificial intelligence (68T27)
Related Items
A decomposition method for CNF minimality proofs, Horn functions and submodular Boolean functions, Properties of quasi-Boolean function on quasi-Boolean algebra, Boolean functions with a simple certificate for CNF complexity, Bidual Horn functions and extensions, Hydras: directed hypergraphs and Horn formulas, Hardness results for approximate pure Horn CNF formulae minimization, A subclass of Horn CNFs optimally compressible in polynomial time, Exclusive and essential sets of implicates of Boolean functions, Generalized domination in closure systems, The multiple facets of the canonical direct unit implicational basis, Horn representation of a concept lattice, Double Horn functions, Recognition of interval Boolean functions, Disjoint essential sets of implicates of a CQ Horn function, Recognition and dualization of disguised bidual Horn functions., Optimal compression of propositional Horn knowledge bases: Complexity and approximation, On functional dependencies in \(q\)-Horn theories
Uses Software
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
