## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

# 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 ...

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required