The joy of implications, aka pure Horn formulas: mainly a survey

DOI10.1016/J.TCS.2016.03.018zbMATH Open1418.03144arXiv1411.6432OpenAlexW1866396423MaRDI QIDQ507516FDOQ507516

Marcel Wild

Publication date: 6 February 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: Apart from a brief look at applications (Relational Databases, Formal Concept Analysis, data mining) this article is devoted to the mathematical t h e o r y of implications (=pure Horn formulas). It is mainly a survey of results obtained in the last thirty years, but features a few novelties as well. Some keywords: The Duquenne-Guiges (implicational) base, the canonical direct base, prime implicates, the consensus method, implications and meet irreducible closed sets, optimum bases for certain lattices, ordered direct bases, generating all closed sets, general (i.e. impure) Horn functions. We pose four open problems to stimulate further research.

Full work available at URL: https://arxiv.org/abs/1411.6432

zbMATH Keywords

minimizationformal concept analysislattice theoryclosure systemconvex geometryuniversal algebrafunctional dependenciesBoolean logicassociation rulemeet-irreduciblesprime implicatespure Horn functions

Mathematics Subject Classification ID

Logic in computer science (03B70)

Cites Work

• Title not available (Why is that?)
• Comparing performance of algorithms for generating concept lattices
• Title not available (Why is that?)
• Title not available (Why is that?)
• Lattice Theory: Foundation
• Title not available (Why is that?)
• Model Theory
• Title not available (Why is that?)
• The core of finite lattices
• Title not available (Why is that?)
• Computing the minimum cover of functional dependencies
• Minimal Representation of Directed Hypergraphs
• Functional Dependencies in a Relational Database and Propositional Logic
• Learning Spaces
• Computing premises of a minimal cover of functional dependencies is intractable
• Fuzzy and rough formal concept analysis: a survey
• Computational aspects of monotone dualization: a brief survey
• The lattices of closure systems, closure operators, and implicational systems on a finite set: A survey
• Subgroup lattices and symmetric functions
• Title not available (Why is that?)
• Hardness results for approximate pure Horn CNF formulae minimization
• Redundancy, Deduction Schemes, and Minimum-Size Bases for Association Rules
• A subclass of Horn CNFs optimally compressible in polynomial time
• Title not available (Why is that?)
• A theory of finite closure spaces based on implications
• Reasoning with models
• Canonical Horn Representations and Query Learning
• On Cores and Prime Implicants of Truth Functions
• The multiple facets of the canonical direct unit implicational basis
• Title not available (Why is that?)
• Consensus algorithms for the generation of all maximal bicliques
• Design by example: An application of Armstrong relations
• Greedoids
• Compactly generating all satisfying truth assignments of a Horn formula
• A characterization theorem for the canonical basis of a closure operator
• THE LATTICE THEORY OF FUNCTIONAL DEPENDENCIES AND NORMAL DECOMPOSITIONS
• An approach to lattice varieties of finite height
• Realization of abstract convex geometries by point configurations
• Finding all closed sets: A general approach
• Lattices, closures systems and implication bases: a survey of structural aspects and algorithms
• Compressed representation of learning spaces
• Horn approximations of empirical data
• Ordered direct implicational basis of a finite closure system
• The prime stems of rooted circuits of closure spaces and minimum implicational bases
• Fast algorithms for implication bases and attribute exploration using proper premises
• Optimum basis of finite convex geometry
• Efficient algorithms for dualizing large-scale hypergraphs
• Lattices of regular closed subsets of closure spaces
• Characterizations of Finite Lattices that are Bounded-Homomqrphic Images or Sublattices of Free Lattices
• Optimal implicational bases for finite modular lattices
• Title not available (Why is that?)
• Title not available (Why is that?)
• Discovery of the \(D\)-basis in binary tables based on hypergraph dualization
• Succinctness and tractability of closure operator representations
• Algorithms for \(k\)-meet-semidistributive lattices
• On the complexity of enumerating pseudo-intents
• On implicational bases of closure systems with unique critical sets.
• Minimum implicational basis for \(\wedge\)-semidistributive lattices
• Some decision and counting problems of the Duquenne-Guigues basis of implications

Cited In (23)

• Compressed representation of learning spaces
• Description of closure operators in convex geometries of segments on the line
• Dualization in lattices given by implicational bases
• Chemically inspired Erdős-Rényi hypergraphs
• A compact representation for modular semilattices and its applications
• Hierarchical decompositions of implicational bases for the enumeration of meet-irreducible elements
• On functional dependencies in \(q\)-Horn theories
• Lattice point of view for argumentation framework
• Translating between the representations of a ranked convex geometry
• Enumerating maximal consistent closed sets in closure systems
• On Dualization over Distributive Lattices
• Direct-optimal basis computation by means of the fusion of simplification rules
• Quasi-closed elements in fuzzy posets
• Polynomial delay hybrid algorithms to enumerate candidate keys for a relation
• On the preferred extensions of argumentation frameworks: bijections with naive sets
• Algorithms for computing the Shapley value of cooperative games on lattices
• Scalable Visual Analytics in FCA
• Decision systems in rough set theory: A set operatorial perspective
• Algorithms for \(k\)-meet-semidistributive lattices
• Directed hypergraphs: introduction and fundamental algorithms -- a survey
• A representation of antimatroids by Horn rules and its application to educational systems
• Convex geometries representable by at most five circles on the plane
• Representation of convex geometries by circles on the plane

This page was built for publication: The joy of implications, aka pure Horn formulas: mainly a survey

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q507516)