9781118914373

A computational perspective on partial order and lattice theory, focusing on algorithms and their applications

This book provides a uniform treatment of the theory and applications of lattice theory. The applications covered include tracking dependency in distributed systems, combinatorics, detecting global predicates in distributed systems, set families, and integer partitions. The book presents algorithmic proofs of theorems whenever possible. These proofs are written in the calculational style advocated by Dijkstra, with arguments explicitly spelled out step by step. The author’s intent is for readers to learn not only the proofs, but the heuristics that guide said proofs.

Introduction to Lattice Theory with Computer Science Applications:

Examines; posets, Dilworth’s theorem, merging algorithms, lattices, lattice completion, morphisms, modular and distributive lattices, slicing, interval orders, tractable posets, lattice enumeration algorithms, and dimension theory
Provides end of chapter exercises to help readers retain newfound knowledge on each subject
Includes supplementary material at www.ece.utexas.edu/~garg

Introduction to Lattice Theory with Computer Science Applications is written for students of computer science, as well as practicing mathematicians.

Vijay K. Garg, PhD, is a Cullen Trust Endowed professor at the University of Texas at Austin. His research focuses on applications of lattice theory to distributed computing. He has worked in the areas of distributed systems and discrete event systems for the past thirty years. Dr. Garg is the author of Elements of Distributed Computing (Wiley, 2002), Concurrent and Distributed Computing in Java (Wiley, 2004) and Modeling and Control of Logical Discrete Event Systems (co-authored with Ratnesh Kumar).

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

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.

Amazon no longer offers textbook rentals. We do!

Introduction to Lattice Theory With Computer Science Applications

Introduction to Lattice Theory With Computer Science Applications

1118914376

Summary

Author Biography

Table of Contents

Supplemental Materials

Write a Review