Introduction to Lattice Theory with Computer Science Applications
Description
Reviews / Votes
"This nice book on lattices and their applications in computer science is written fromthe perspective of a computer scientist rather than a mathematician...Given its emphasis on algorithms and their complexity, itseems to be mainly intended for students of computer science and engineering. Theauthor's approach is based on the premise that a student needs to learn the heuristicsthat guide the proofs, besides the proofs themselves, and to learn ways to extend andanalyze theorems...One of the most important and valuable features of the book is its focus on applicationsof lattice theory. The author intends to treat applications on par with the theory." Altogether a "lovely book". (Mathematical Reviews/MathSciNet April 2017)More details
Other editions
Additional editions
Person
Content
List of Figures xiii
Nomenclature xv
Preface xvii
1 Introduction 1
1.1 Introduction 1
1.2 Relations 2
1.3 Partial Orders 3
1.4 Join and Meet Operations 5
1.5 Operations on Posets 7
1.6 Ideals and Filters 8
1.7 Special Elements in Posets 9
1.8 Irreducible Elements 10
1.9 Dissector Elements 11
1.10 Applications: Distributed Computations 11
1.11 Applications: Combinatorics 12
1.12 Notation and Proof Format 13
1.13 Problems 15
1.14 Bibliographic Remarks 15
2 Representing Posets 17
2.1 Introduction 17
2.2 Labeling Elements of The Poset 17
2.3 Adjacency List Representation 18
2.4 Vector Clock Representation 20
2.5 Matrix Representation 22
2.6 Dimension-Based Representation 22
2.7 Algorithms to Compute Irreducibles 23
2.8 Infinite Posets 24
2.9 Problems 26
2.10 Bibliographic Remarks 27
3 Dilworth's Theorem 29
3.1 Introduction 29
3.2 Dilworth's Theorem 29
3.3 Appreciation of Dilworth's Theorem 30
3.4 Dual of Dilworth's Theorem 32
3.5 Generalizations of Dilworth's Theorem 32
3.6 Algorithmic Perspective of Dilworth's Theorem 32
3.7 Application: Hall's Marriage Theorem 33
3.8 Application: Bipartite Matching 34
3.9 Online Decomposition of Posets 35
3.10 A Lower Bound on Online Chain Partition 37
3.11 Problems 38
3.12 Bibliographic Remarks 39
4 Merging Algorithms 41
4.1 Introduction 41
4.2 Algorithm to Merge Chains in Vector Clock Representation 41
4.3 An Upper Bound for Detecting an Antichain of Size K 47
4.4 A Lower Bound for Detecting an Antichain of Size K 48
4.5 An Incremental Algorithm for Optimal Chain Decomposition 50
4.6 Problems 50
4.7 Bibliographic Remarks 51
5 Lattices 53
5.1 Introduction 53
5.2 Sublattices 54
5.3 Lattices as Algebraic Structures 55
5.4 Bounding The Size of The Cover Relation of a Lattice 56
5.5 Join-Irreducible Elements Revisited 57
5.6 Problems 59
5.7 Bibliographic Remarks 60
6 Lattice Completion 61
6.1 Introduction 61
6.2 Complete Lattices 61
6.3 Closure Operators 62
6.4 Topped n-Structures 63
6.5 Dedekind-Macneille Completion 64
6.6 Structure of Dedekind--Macneille Completion of a Poset 67
6.7 An Incremental Algorithm for Lattice Completion 69
6.8 Breadth First Search Enumeration of Normal Cuts 71
6.9 Depth First Search Enumeration of Normal Cuts 73
6.10 Application: Finding the Meet and Join of Events 75
6.11 Application: Detecting Global Predicates in Distributed Systems 76
6.12 Application: Data Mining 77
6.13 Problems 78
6.14 Bibliographic Remarks 78
7 Morphisms 79
7.1 Introduction 79
7.2 Lattice Homomorphism 79
7.3 Lattice Isomorphism 80
7.4 Lattice Congruences 82
7.5 Quotient Lattice 83
7.6 Lattice Homomorphism and Congruence 83
7.7 Properties of Lattice Congruence Blocks 84
7.8 Application: Model Checking on Reduced Lattices 85
7.9 Problems 89
7.10 Bibliographic Remarks 90
8 Modular Lattices 91
8.1 Introduction 91
8.2 Modular Lattice 91
8.3 Characterization of Modular Lattices 92
8.4 Problems 98
8.5 Bibliographic Remarks 98
9 Distributive Lattices 99
9.1 Introduction 99
9.2 Forbidden Sublattices 99
9.3 Join-Prime Elements 100
9.4 Birkhoff's Representation Theorem 101
9.5 Finitary Distributive Lattices 104
9.6 Problems 104
9.7 Bibliographic Remarks 105
10 Slicing 107
10.1 Introduction 107
10.2 Representing Finite Distributive Lattices 107
10.3 Predicates on Ideals 110
10.4 Application: Slicing Distributed Computations 116
10.5 Problems 117
10.6 Bibliographic Remarks 118
11 Applications of Slicing to Combinatorics 119
11.1 Introduction 119
11.2 Counting Ideals 120
11.3 Boolean Algebra and Set Families 121
11.4 Set Families of Size k 122
11.5 Integer Partitions 123
11.6 Permutations 127
11.7 Problems 129
11.8 Bibliographic Remarks 129
12 Interval Orders 131
12.1 Introduction 131
12.2 Weak Order 131
12.3 Semiorder 133
12.4 Interval Order 134
12.5 Problems 136
12.6 Bibliographic Remarks 137
13 Tractable Posets 139
13.1 Introduction 139
13.2 Series-Parallel Posets 139
13.3 Two-Dimensional Posets 142
13.4 Counting Ideals of a Two-Dimensional Poset 145
13.5 Problems 146
13.6 Bibliographic Remarks 147
14 Enumeration Algorithms 149
14.1 Introduction 149
14.2 BFS Traversal 150
14.3 DFS Traversal 154
14.4 LEX Traversal 154
14.5 Uniflow Partition of Posets 160
14.6 Enumerating Tuples of Product Spaces 163
14.7 Enumerating All Subsets 163
14.8 Enumerating All Subsets of Size k 165
14.9 Enumerating Young's Lattice 166
14.10 Enumerating Permutations 167
14.11 Lexical Enumeration of All Order Ideals of a Given Rank 168
14.12 Problems 172
14.13 Bibliographic Remarks 173
15 Lattice of Maximal Antichains 159
15.1 Introduction 159
15.2 Maximal Antichain Lattice 161
15.3 An Incremental Algorithm Based on Union Closure 163
15.4 An Incremental Algorithm Based on BFS 165
15.5 Traversal of the Lattice of Maximal Antichains 166
15.6 Application: Detecting Antichain-Consistent Predicates 168
15.7 Construction and Enumeration of Width Antichain Lattice 169
15.8 Lexical Enumeration of Closed Sets 171
15.9 Construction of Lattices Based on Union Closure 174
15.10 Problems 174
15.11 Bibliographic Remarks 175
16 Dimension Theory 177
16.1 Introduction 177
16.2 Chain Realizers 178
16.3 Standard Examples of Dimension Theory 179
16.4 Relationship Between the Dimension and the Width of a Poset 180
16.5 Removal Theorems for Dimension 181
16.6 Critical Pairs in the Poset 182
16.7 String Realizers 184
16.8 Rectangle Realizers 193
16.9 Order Decomposition Method and Its Applications 194
16.10 Problems 196
16.11 Bibliographic Remarks 197
17 Fixed Point Theory 215
17.1 Complete Partial Orders 215
17.2 Knaster-Tarski Theorem 216
17.3 Application: Defining Recursion Using Fixed Points 218
17.4 Problems 226
17.5 Bibliographic Remarks 227
Bibliography 229
Index 235
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...
