Chapter 10Slicing
10.1 Introduction
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.
10.2 Representing Finite Distributive Lattices
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 ...
Get Introduction to Lattice Theory with Computer Science Applications now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
