Introduction to Lattice Theory with Computer Science Applications

List Of Figures

Figure 1.1	The graph of a relation
Figure 1.2	Hasse diagram
Figure 1.3	Only the first two posets are lattices
Figure 1.4	(a) Pentagon(N5) and (b) diamond(M3)
Figure 1.5	Cross product of posets
Figure 1.6	A computation in the happened-before model
Figure 1.7	Ferrer's diagram for (4,3,2) shown to contain (2,2,2)
Figure 1.8	Young's lattice for (3,3,3)
Figure 2.1	Adjacency list representation of a poset
Figure 2.2	Vector clock labeling of a poset for a distributed computation
Figure 2.3	Vector clock algorithm
Figure 2.4	(a) An antichain of size 5 and (b) its two linear extensions
Figure 2.5	(a,b) Trivial examples of p-diagrams
Figure 2.6	(a) A p-diagram and (b) its corresponding infinite poset
Figure 3.1	Decomposition of P into t chains
Figure 3.2	Hall's Marriage Theorem
Figure 3.3	A poset of width 2 forcing an algorithm to use three chains for decomposition
Figure 3.4	Chain partitioning algorithm
Figure 4.1	Function that determines if an antichain of size k exists
Figure 4.2	An example of a failed naive strategy. (a) The initial configuration. (b) The point at which the strategy fails: there is nowhere to insert (2,0,0). (c) This example can be merged into two chains
Figure 4.3	Generalized merge procedure for deposets
Figure 4.4	Function FindQ that finds the output queue to insert an element
Figure 4.5	Using a queue insert graph to find the output queue
Figure 4.6	Algorithm for the adversary
Figure 5.1	Examples: lattices and sublattices
Figure 5.2	Table notation for the algebra (X, ⊔ , ...