Saturday, September 14, 2013

Ranking elements of distributive lattices

There is a correspondence between the number of join irreducibles contained in an element of a distributive lattice and its ordinal height minus one:
(= (dec (count [1 1 1 1]))
   (count #{#{} #{#{}} #{#{} #{#{}}}}))
The same principle applies to multisets which are elements of a distributive inclusion lattice:
(= (rank {:x 1, :y 2})
   (dec (count [1 2 2 1]))
   (count #{{:x 1} {:y 1} {:y 2}))
This implies that we can use the idea of join irreducible elements as a basis for structured multisets and canonical forms of structures. A canonical labeling of a structure is one over a set-theoretic natural number such as #{#{} #{#{}} #{#{} #{#{}}}} and a structured multiset is a structure over the join irreducibles of the multiset. The key is to implement an effective partial canonization technique so that we can properly determine the equality of such structures.

No comments:

Post a Comment