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

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.

This version is near identical to the accepted version in Theoretical Computer Science

References in corpus (1)

• Discovery of the $D$-basis in binary tables based on hypergraph dualization

Cited by in corpus (8)

• Representation of convex geometries by circles on a plane
• On Dualization over Distributive Lattices
• A Compact Representation for Modular Semilattices and its Applications
• ALLSAT compressed with wildcards: From CNF's to orthogonal DNF's by imposing the clauses one by one
• Convex geometries representable by at most 5 circles on the plane
• The Horn Non-Clausal Class and its Polynomiality
• Description of closure operators in convex geometries of segments on a line
• Hierarchical Decompositions of dihypergraphs