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, ? , ? ) Figure 5.3 Join-irreducible elements: J(L)={a, b, c, d} Figure 6.1 (a) A poset. (b) Its completion (the unshaded vertex is the added element) Figure 6.2 A poset that is not a complete lattice Figure 6.3 The DM completion of the poset from Figure 6.2 Figure 6.4 Two posets and their DM completions Figure 6.5 The complete lattice via order ideals that embeds the poset from Figure 6.4(b) Figure 6.6 Incremental algorithm IDML for DM construction Figure 6.7 Algorithm BFS-DML for BFS enumeration of DM-Lattice Figure 6.8 Algorithm DFS-DML for DFS enumeration of DM-lattice Figure 6.9 (a) The original poset. (b) Equivalent representation using vector clocks. (c) Its Lattice of normal cuts Figure 7.1 Monotone f Figure 7.2 Fundamental Homomorphism Theorem Figure 7.3 (a,b) Quadrilateral-closed structures Figure 7.4 Simple reduction of state graph does not preserve path based formulas Figure 7.5 (a,b) Proof of Lemma 7.13 Figure 7.6 Proof of Lemma 7.14 Figure 8.1 Proof of Theorem 8.5 Figure 8.2 Theorem 8.9 Figure 8.3 (a) A ranked poset, (b) A poset that is not ranked, (c) A ranked and graded poset, and (d) A ranked and graded lattice Figure 9.1 Diamond M3-a nondistributive lattice Figure 9.2 A lattice L, its set of join-irreducibles J(L), and their ideals LI (J(L)) Figure 9.3 A lattice with the "N-poset" as the set of join-irreducibles Figure 9.4 (a) Poset of Join- ("j") and meet- ("m") irreducible elements are isomorphic; (b) Irreducibles in a nondistributive lattice Figure 10.1 (a) P: A partial order. (b) The lattice of ideals. (c) The directed graph P´ Figure 10.2 (a) A directed graph and (b) the lattice of its nontrivial ideals Figure 10.3 (a) The poset or directed graph K for generating subsets of X of size k. (b) The ideal denoting the subset {1,3,4} Figure 10.4 Graphs and slices for generating subsets of X when |X| = 4 Figure 10.5 An efficient algorithm to detect a linear predicate Figure 10.6 An efficient algorithm to compute the slice for a predicate B Figure 10.7 An efficient algorithm to compute the slice for a linear predicate B Figure 11.1 Graphs and slices for generating subsets of X when |X| = 4 Figure 11.2 Slice for the predicate "does not contain consecutive numbers" Figure 11.3 Ferrer's diagram for the integer partition (4,2,1) for 7 Figure 11.4 An Application of Ferrer's diagram Figure 11.5 Young's lattice for (3,3,3) Figure 11.6 The poset corresponding to Ferrer's diagram of (3,3,3) Figure 11.7 Slice for d2 = 2 Figure 11.8 Slice for "distinct parts." Figure 11.9 Poset T(5). Figure 11.10 Slice for subsets of permutations Figure 12.1 A poset that is a ranking Figure 12.2 Examples of weak orders (or rankings.) Figure 12.3 A poset and its normal ranking extension Figure 12.4 Mapping elements of poset to interval order Figure 13.1 Example series and parallel compositions. (a-c) Posets. (d) Result of P2 + P3. (e) Result of P1 * (P2 + P3) Figure 13.2 (a) An SP tree for the poset in Figure 13.1(e). (b) The conjugate SP tree. (c) The conjugate poset Figure 13.3 (a) A two-dimensional poset. (b) Its comparability graph G. (c) GC. (d) A valid conjugate for the original poset Figure 13.4 The poset S3 Figure 13.5 (a) is a non-separating linear extension of the partial order (b), when at least one of the dotted edges holds Figure 13.6 A two-dimensional Poset P=(X,?p) Figure 13.7 Conjugate Q = L1 n L2-1 of the poset P Figure 13.8 The order imposed by ?p ? ?Q Figure 13.9 A partial order P that has a nonseparating linear extension Figure 14.1 (a) A computation. (b) Its lattice of consistent global states. (c) Traversals of the lattice Figure 14.2 BFS enumeration of CGS Figure 14.3 A vector clock based BFS enumeration of CGS Figure 14.4 A vector clock based DFS enumeration of CGS Figure 14.5 An algorithm for lexical traversal of all ideals of a poset with any chain partition Figure 14.6 L(3,3) with example of an ideal Figure...