Representing lattices using many-valued relations

Abstract: This paper provides a representation theorem of lattices using many-valued relations. We show that any many-valued relation can be associated to a unique lattice which is a meet-sublattice of a product of chains. Conversely, to any lattice we can associate a many-valued relation such that its associated lattice is isomorphic to the initial one. Thereby, we obtain a representation theorem of lattices using many-valued relations. Moreover, since several many-valued relations might have the same associated lattice, we give a characterization of the minimal many-valued relation that can be associated to a lattice. We then sketch a polynomial time algorithm which computes such a minimal relation from either a lattice or an arbitrary relation. This representation presents several advantages: it is smaller than the usual binary representation; all known reconstruction algorithms working on binary relation can be used without loss of efficiency; it can be used by existing data mining processes. [Copyright &y& Elsevier]