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 c10-math-0001 can be equivalently represented by the poset of the join-irreducible elements of c10-math-0002 (and constructing all the down-sets of that poset). Given any subset c10-math-0003 of c10-math-0004, 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 O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.