Read more
Informationen zum Autor 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). Klappentext A computational perspective on partial order and lattice theory, focusing on algorithms and their applicationsThis 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 also the heuristics that guide these 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/~gargIntroduction to Lattice Theory with Computer Science Applications is written for students of computer science, as well as for practicing mathematicians. Zusammenfassung 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. Inhaltsverzeichnis 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 ...
