Optimal compression of propositional Horn knowledge bases: Complexity and approximation
From MaRDI portal
Publication:1313951
DOI10.1016/0004-3702(93)90062-GzbMath0935.68105MaRDI QIDQ1313951
Alexander Kogan, Peter L. Hammer
Publication date: 24 April 2000
Published in: Artificial Intelligence (Search for Journal in Brave)
Related Items
Known and new classes of generalized Horn formulae with polynomial recognition and SAT testing ⋮ Redundancy in logic. II: 2CNF and Horn propositional formulae ⋮ Redundancy in logic. III: Non-monotonic reasoning ⋮ A decomposition method for CNF minimality proofs ⋮ Unique key Horn functions ⋮ The algebraic structure of the densification and the sparsification tasks for CSPs ⋮ Boolean functions with a simple certificate for CNF complexity ⋮ Relations between threshold and \(k\)-interval Boolean functions ⋮ Properties of Switch-List Representations of Boolean Functions ⋮ Bidual Horn functions and extensions ⋮ Boolean functions with long prime implicants ⋮ Algorithms for computing minimal equivalent subformulas ⋮ Redundancy in logic. I: CNF propositional formulae ⋮ Bounds on the size of PC and URC formulas ⋮ Hydras: complexity on general graphs and a subclass of trees ⋮ Hydras: directed hypergraphs and Horn formulas ⋮ Recognition of tractable DNFs representable by a constant number of intervals ⋮ 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 ⋮ Pseudo-models and propositional Horn inference ⋮ Translating between the representations of a ranked convex geometry ⋮ Double Horn functions ⋮ An efficient algorithm for Horn description ⋮ Disjoint essential sets of implicates of a CQ Horn function ⋮ On the hydra number of disconnected graphs ⋮ Approximating Minimum Representations of Key Horn Functions ⋮ On functional dependencies in \(q\)-Horn theories
Cites Work
