O'Reilly logo

Introduction to Lattice Theory with Computer Science Applications by Vijay K. Garg

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

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

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

Start Free Trial

No credit card required