In many applications, we are required to enumerate a subset of a given set that satisfies a given property. For example, in a distributed computation, we may be interested in all global states such that they satisfy a given formula (such as violation of mutual exclusion). While studying integer partitions, we may be interested in only those partitions in which the first two parts are equal. In this chapter, we present a method based on finite distributive lattices that allows us to analyze such subsets. This method, called slicing, enables us to produce structures that generate subsets of the finite distributive lattice.

From Birkhoff's representation theorem, every finite distributive lattice can be equivalently represented by the poset of the join-irreducible elements of (and constructing all the down-sets of that poset). Given any subset of , our goal is to compute the poset that represents the smallest sublattice containing . For this purpose, we use directed graphs instead of posets to represent ...

Start Free Trial

No credit card required