Horn representation of a concept lattice
Concept lattices are the central notion of formal concept analysis. They are applied in many different areas such as data mining, knowledge representation or ontology engineering and are subject to ongoing research. In order to better understand the nature of concept lattices, it is useful to consider their links to other mathematical notions. For example, a concept lattice can be viewed as a special kind of poset or closure system. In this paper, we consider another view of concept lattices by establishing a link to propositional formulae and a special closure property of relations. The main result is an elementary derivation of a Horn formula that uniquely represents a concept lattice based on prime implicates. Using the derived Horn representation, we re-establish the #P-completeness of the concept counting problem and find that the Horn representation is closely related to the stem base of a concept lattice.
concept lattice prime implicates horn conjunctive normal form formula attribute implications