Introduction to Lattice Theory with Computer Science Applications

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

"This nice book on lattices and their applications in computer science is written from the perspective of a computer scientist rather than a mathematician...Given its emphasis on algorithms and their complexity, it seems to be mainly intended for students of computer science and engineering. The author's approach is based on the premise that a student needs to learn the heuristics that guide the proofs, besides the proofs themselves, and to learn ways to extend and analyze theorems...One of the most important and valuable features of the book is its focus on applications of lattice theory. The author intends to treat applications on par with the theory." Altogether a "lovely book". (Mathematical Reviews/MathSciNet April 2017)

• List of Figures xiiiNomenclature xvPreface xvii1 Introduction 11.1 Introduction 11.2 Relations 21.3 Partial Orders 31.4 Join and Meet Operations 51.5 Operations on Posets 71.6 Ideals and Filters 81.7 Special Elements in Posets 91.8 Irreducible Elements 101.9 Dissector Elements 111.10 Applications: Distributed Computations 111.11 Applications: Combinatorics 121.12 Notation and Proof Format 131.13 Problems 151.14 Bibliographic Remarks 152 Representing Posets 172.1 Introduction 172.2 Labeling Elements of The Poset 172.3 Adjacency List Representation 182.4 Vector Clock Representation 202.5 Matrix Representation 222.6 Dimension-Based Representation 222.7 Algorithms to Compute Irreducibles 232.8 Infinite Posets 242.9 Problems 262.10 Bibliographic Remarks 273 Dilworth’s Theorem 293.1 Introduction 293.2 Dilworth’s Theorem 293.3 Appreciation of Dilworth’s Theorem 303.4 Dual of Dilworth’s Theorem 323.5 Generalizations of Dilworth’s Theorem 323.6 Algorithmic Perspective of Dilworth’s Theorem 323.7 Application: Hall’s Marriage Theorem 333.8 Application: Bipartite Matching 343.9 Online Decomposition of Posets 353.10 A Lower Bound on Online Chain Partition 373.11 Problems 383.12 Bibliographic Remarks 394 Merging Algorithms 414.1 Introduction 414.2 Algorithm to Merge Chains in Vector Clock Representation 414.3 An Upper Bound for Detecting an Antichain of Size K 474.4 A Lower Bound for Detecting an Antichain of Size K 484.5 An Incremental Algorithm for Optimal Chain Decomposition 504.6 Problems 504.7 Bibliographic Remarks 515 Lattices 535.1 Introduction 535.2 Sublattices 545.3 Lattices as Algebraic Structures 555.4 Bounding The Size of The Cover Relation of a Lattice 565.5 Join-Irreducible Elements Revisited 575.6 Problems 595.7 Bibliographic Remarks 606 Lattice Completion 616.1 Introduction 616.2 Complete Lattices 616.3 Closure Operators 626.4 Topped ∩-Structures 636.5 Dedekind–Macneille Completion 646.6 Structure of Dedekind--Macneille Completion of a Poset 676.7 An Incremental Algorithm for Lattice Completion 696.8 Breadth First Search Enumeration of Normal Cuts 716.9 Depth First Search Enumeration of Normal Cuts 736.10 Application: Finding the Meet and Join of Events 756.11 Application: Detecting Global Predicates in Distributed Systems 766.12 Application: Data Mining 776.13 Problems 786.14 Bibliographic Remarks 787 Morphisms 797.1 Introduction 797.2 Lattice Homomorphism 797.3 Lattice Isomorphism 807.4 Lattice Congruences 827.5 Quotient Lattice 837.6 Lattice Homomorphism and Congruence 837.7 Properties of Lattice Congruence Blocks 847.8 Application: Model Checking on Reduced Lattices 857.9 Problems 897.10 Bibliographic Remarks 908 Modular Lattices 918.1 Introduction 918.2 Modular Lattice 918.3 Characterization of Modular Lattices 928.4 Problems 988.5 Bibliographic Remarks 989 Distributive Lattices 999.1 Introduction 999.2 Forbidden Sublattices 999.3 Join-Prime Elements 1009.4 Birkhoff’s Representation Theorem 1019.5 Finitary Distributive Lattices 1049.6 Problems 1049.7 Bibliographic Remarks 10510 Slicing 10710.1 Introduction 10710.2 Representing Finite Distributive Lattices 10710.3 Predicates on Ideals 11010.4 Application: Slicing Distributed Computations 11610.5 Problems 11710.6 Bibliographic Remarks 11811 Applications of Slicing to Combinatorics 11911.1 Introduction 11911.2 Counting Ideals 12011.3 Boolean Algebra and Set Families 12111.4 Set Families of Size k 12211.5 Integer Partitions 12311.6 Permutations 12711.7 Problems 12911.8 Bibliographic Remarks 12912 Interval Orders 13112.1 Introduction 13112.2 Weak Order 13112.3 Semiorder 13312.4 Interval Order 13412.5 Problems 13612.6 Bibliographic Remarks 13713 Tractable Posets 13913.1 Introduction 13913.2 Series–Parallel Posets 13913.3 Two-Dimensional Posets 14213.4 Counting Ideals of a Two-Dimensional Poset 14513.5 Problems 14613.6 Bibliographic Remarks 14714 Enumeration Algorithms 14914.1 Introduction 14914.2 BFS Traversal 15014.3 DFS Traversal 15414.4 LEX Traversal 15414.5 Uniflow Partition of Posets 16014.6 Enumerating Tuples of Product Spaces 16314.7 Enumerating All Subsets 16314.8 Enumerating All Subsets of Size k 16514.9 Enumerating Young’s Lattice 16614.10 Enumerating Permutations 16714.11 Lexical Enumeration of All Order Ideals of a Given Rank 16814.12 Problems 17214.13 Bibliographic Remarks 17315 Lattice of Maximal Antichains 15915.1 Introduction 15915.2 Maximal Antichain Lattice 16115.3 An Incremental Algorithm Based on Union Closure 16315.4 An Incremental Algorithm Based on BFS 16515.5 Traversal of the Lattice of Maximal Antichains 16615.6 Application: Detecting Antichain-Consistent Predicates 16815.7 Construction and Enumeration of Width Antichain Lattice 16915.8 Lexical Enumeration of Closed Sets 17115.9 Construction of Lattices Based on Union Closure 17415.10 Problems 17415.11 Bibliographic Remarks 17516 Dimension Theory 17716.1 Introduction 17716.2 Chain Realizers 17816.3 Standard Examples of Dimension Theory 17916.4 Relationship Between the Dimension and the Width of a Poset 18016.5 Removal Theorems for Dimension 18116.6 Critical Pairs in the Poset 18216.7 String Realizers 18416.8 Rectangle Realizers 19316.9 Order Decomposition Method and Its Applications 19416.10 Problems 19616.11 Bibliographic Remarks 19717 Fixed Point Theory 21517.1 Complete Partial Orders 21517.2 Knaster–Tarski Theorem 21617.3 Application: Defining Recursion Using Fixed Points 21817.4 Problems 22617.5 Bibliographic Remarks 227Bibliography 229Index 235