Introduction to Lattice Theory with Computer Science Applications

Introduction to Lattice Theory with Computer Science Applications

by Vijay K. Garg
Released May 2015
Publisher(s): Wiley
ISBN: 9781118914373

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

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.

    Table of contents

    1. Cover
    2. Title Page
    3. Copyright
    4. Dedication
    5. List Of Figures
    6. Nomenclature
    7. Preface
    8. Chapter 1: Introduction
      1. 1.1 Introduction
      2. 1.2 Relations
      3. 1.3 Partial Orders
      4. 1.4 Join and Meet Operations
      5. 1.5 Operations on Posets
      6. 1.6 Ideals and Filters
      7. 1.7 Special Elements in Posets
      8. 1.8 Irreducible Elements
      9. 1.9 Dissector Elements
      10. 1.10 Applications: Distributed Computations
      11. 1.11 Applications: Combinatorics
      12. 1.12 Notation and Proof Format
      13. 1.13 Problems
      14. 1.14 Bibliographic Remarks
    9. Chapter 2: Representing Posets
      1. 2.1 Introduction
      2. 2.2 Labeling Elements of The Poset
      3. 2.3 Adjacency List Representation
      4. 2.4 Vector Clock Representation
      5. 2.5 Matrix Representation
      6. 2.6 Dimension-Based Representation
      7. 2.7 Algorithms to Compute Irreducibles
      8. 2.8 Infinite Posets
      9. 2.9 Problems
      10. 2.10 Bibliographic Remarks
    10. Chapter 3: Dilworth's Theorem
      1. 3.1 Introduction
      2. 3.2 Dilworth's Theorem
      3. 3.3 Appreciation of Dilworth's Theorem
      4. 3.4 Dual of Dilworth's Theorem
      5. 3.5 Generalizations of Dilworth's Theorem
      6. 3.6 Algorithmic Perspective of Dilworth's Theorem
      7. 3.7 Application: Hall's Marriage Theorem
      8. 3.8 Application: Bipartite Matching
      9. 3.9 Online Decomposition of posets
      10. 3.10 A Lower Bound on Online Chain Partition
      11. 3.11 Problems
      12. 3.12 Bibliographic Remarks
    11. Chapter 4: Merging Algorithms
      1. 4.1 Introduction
      2. 4.2 Algorithm to Merge Chains in Vector Clock Representation
      3. 4.3 An Upper Bound for Detecting an Antichain of Size
      4. 4.4 A Lower Bound for Detecting an Antichain of Size
      5. 4.5 An Incremental Algorithm for Optimal Chain Decomposition
      6. 4.6 Problems
      7. 4.7 Bibliographic Remarks
    12. Chapter 5: Lattices
      1. 5.1 Introduction
      2. 5.2 Sublattices
      3. 5.3 Lattices as Algebraic Structures
      4. 5.4 Bounding The Size of The Cover Relation of a Lattice
      5. 5.5 Join-Irreducible Elements Revisited
      6. 5.6 Problems
      7. 5.7 Bibliographic Remarks
    13. Chapter 6: Lattice Completion
      1. 6.1 INTRODUCTION
      2. 6.2 COMPLETE LATTICES
      3. 6.3 CLOSURE OPERATORS
      4. 6.4 TOPPED –STRUCTURES
      5. 6.5 DEDEKIND–MACNEILLE COMPLETION
      6. 6.6 STRUCTURE OF DEDEKIND—MACNEILLE COMPLETION OF A POSET
      7. 6.7 AN INCREMENTAL ALGORITHM FOR LATTICE COMPLETION
      8. 6.8 BREADTH FIRST SEARCH ENUMERATION OF NORMAL CUTS
      9. 6.9 DEPTH FIRST SEARCH ENUMERATION OF NORMAL CUTS
      10. 6.10 APPLICATION: FINDING THE MEET AND JOIN OF EVENTS
      11. 6.11 APPLICATION: DETECTING GLOBAL PREDICATES IN DISTRIBUTED SYSTEMS
      12. 6.12 APPLICATION: DATA MINING
      13. 6.13 PROBLEMS
      14. 6.14 BIBLIOGRAPHIC REMARKS
    14. Chapter 7: Morphisms
      1. 7.1 INTRODUCTION
      2. 7.2 LATTICE HOMOMORPHISM
      3. 7.3 LATTICE ISOMORPHISM
      4. 7.4 LATTICE CONGRUENCES
      5. 7.5 QUOTIENT LATTICE
      6. 7.6 LATTICE HOMOMORPHISM AND CONGRUENCE
      7. 7.7 PROPERTIES OF LATTICE CONGRUENCE BLOCKS
      8. 7.8 APPLICATION: MODEL CHECKING ON REDUCED LATTICES
      9. 7.9 PROBLEMS
      10. 7.10 BIBLIOGRAPHIC REMARKS
    15. Chapter 8: Modular Lattices
      1. 8.1 INTRODUCTION
      2. 8.2 MODULAR LATTICE
      3. 8.3 CHARACTERIZATION OF MODULAR LATTICES
      4. 8.4 PROBLEMS
      5. 8.5 BIBLIOGRAPHIC REMARKS
    16. Chapter 9: Distributive Lattices
      1. 9.1 INTRODUCTION
      2. 9.2 FORBIDDEN SUBLATTICES
      3. 9.3 JOIN-PRIME ELEMENTS
      4. 9.4 BIRKHOFF'S REPRESENTATION THEOREM
      5. 9.5 FINITARY DISTRIBUTIVE LATTICES
      6. 9.6 PROBLEMS
      7. 9.7 BIBLIOGRAPHIC REMARKS
    17. Chapter 10: Slicing
      1. 10.1 Introduction
      2. 10.2 Representing Finite Distributive Lattices
      3. 10.3 Predicates on Ideals
      4. 10.4 Application: Slicing Distributed Computations
      5. 10.5 Problems
      6. 10.6 Bibliographic Remarks
    18. Chapter 11: Applications of Slicing to Combinatorics
      1. 11.1 Introduction
      2. 11.2 Counting Ideals
      3. 11.3 Boolean Algebra and Set Families
      4. 11.4 Set Families of Size
      5. 11.5 Integer Partitions
      6. 11.6 Permutations
      7. 11.7 Problems
      8. 11.8 Bibliographic Remarks
    19. Chapter 12: Interval Orders
      1. 12.1 Introduction
      2. 12.2 Weak Order
      3. 12.3 Semiorder
      4. 12.4 Interval Order
      5. 12.5 Problems
      6. 12.6 Bibliographic Remarks
    20. Chapter 13: Tractable posets
      1. 13.1 Introduction
      2. 13.2 Series–Parallel Posets
      3. 13.3 Two-Dimensional Posets
      4. 13.4 Counting Ideals of A Two-Dimensional Poset
      5. 13.5 Problems
      6. 13.6 Bibliographic Remarks
    21. Chapter 14: Enumeration Algorithms
      1. 14.1 Introduction
      2. 14.2 BFS Traversal
      3. 14.3 DFS Traversal
      4. 14.4 Lex Traversal
      5. 14.5 Uniflow Partition of Posets
      6. 14.6 Enumerating Tuples of Product Spaces
      7. 14.7 Enumerating all Subsets
      8. 14.8 Enumerating all Subsets of Size
      9. 14.9 Enumerating Young'S Lattice
      10. 14.10 Enumerating Permutations
      11. 14.11 Lexical Enumeration of all Order Ideals of A Given Rank
      12. 14.12 Problems
      13. 14.13 Bibliographic Remarks
    22. Chapter 15: Lattice of Maximal Antichains
      1. 15.1 Introduction
      2. 15.2 Maximal Antichain Lattice
      3. 15.3 An Incremental Algorithm Based on Union Closure
      4. 15.4 An Incremental Algorithm Based on BFS
      5. 15.5 Traversal of The Lattice of Maximal Antichains
      6. 15.6 Application: Detecting Antichain-Consistent Predicates
      7. 15.7 Construction and Enumeration of Width Antichain Lattice
      8. 15.8 Lexical Enumeration of Closed Sets
      9. 15.9 Construction of Lattices Based on Union Closure
      10. 15.10 Problems
      11. 15.11 Bibliographic Remarks
    23. Chapter 16: Dimension Theory
      1. 16.1 Introduction
      2. 16.2 Chain Realizers
      3. 16.3 Standard Examples of Dimension Theory
      4. 16.4 Relationship Between The Dimension and The Width of A Poset
      5. 16.5 Removal Theorems for Dimension
      6. 16.6 Critical Pairs in The Poset
      7. 16.7 String Realizers
      8. 16.8 Rectangle Realizers
      9. 16.9 Order Decomposition Method and Its Applications
      10. 16.10 Problems
      11. 16.11 Bibliographic Remarks
    24. Chapter 17: Fixed Point Theory
      1. 17.1 Complete Partial Orders
      2. 17.2 Knaster–Tarski Theorem
      3. 17.3 Application: Defining Recursion Using Fixed Points
      4. 17.4 Problems
      5. 17.5 Bibliographic Remarks
    25. Bibliography
    26. Index
    27. End User License Agreement

    Product information

    • Title: Introduction to Lattice Theory with Computer Science Applications
    • Author(s): Vijay K. Garg
    • Release date: May 2015
    • Publisher(s): Wiley
    • ISBN: 9781118914373