Introduction to lattice theory with computer science applications
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, detectin...
| Main Author: | |
|---|---|
| Format: | eBook |
| Language: | English |
| Published: |
Hoboken, New Jersey
Wiley
2015
|
| Subjects: | |
| Online Access: | |
| Collection: | O'Reilly - Collection details see MPG.ReNa |
Table of Contents:
- 2.3 Adjacency List Representation2.4 Vector Clock Representation; 2.5 Matrix Representation; 2.6 Dimension-Based Representation; 2.7 Algorithms to Compute Irreducibles; 2.8 Infinite Posets; 2.9 Problems; 2.10 Bibliographic Remarks; Chapter 3: Dilworth's Theorem; 3.1 Introduction; 3.2 Dilworth's Theorem; 3.3 Appreciation of Dilworth's Theorem; 3.4 Dual of Dilworth's Theorem; 3.5 Generalizations of Dilworth's Theorem; 3.6 Algorithmic Perspective of Dilworth's Theorem; 3.7 Application: Hall's Marriage Theorem; 3.8 Application: Bipartite Matching; 3.9 Online Decomposition of posets
- Includes bibliographical references and index
- 5.5 Join-Irreducible Elements Revisited5.6 Problems; 5.7 Bibliographic Remarks; Chapter 6: Lattice Completion; 6.1 INTRODUCTION; 6.2 COMPLETE LATTICES; 6.3 CLOSURE OPERATORS; 6.4 TOPPED -STRUCTURES; 6.5 DEDEKIND-MACNEILLE COMPLETION; 6.6 STRUCTURE OF DEDEKIND-MACNEILLE COMPLETION OF A POSET; 6.7 AN INCREMENTAL ALGORITHM FOR LATTICE COMPLETION; 6.8 BREADTH FIRST SEARCH ENUMERATION OF NORMAL CUTS; 6.9 DEPTH FIRST SEARCH ENUMERATION OF NORMAL CUTS; 6.10 APPLICATION: FINDING THE MEET AND JOIN OF EVENTS; 6.11 APPLICATION: DETECTING GLOBAL PREDICATES IN DISTRIBUTED SYSTEMS.
- 6.12 APPLICATION: DATA MINING6.13 PROBLEMS; 6.14 BIBLIOGRAPHIC REMARKS; Chapter 7: Morphisms; 7.1 INTRODUCTION; 7.2 LATTICE HOMOMORPHISM; 7.3 LATTICE ISOMORPHISM; 7.4 LATTICE CONGRUENCES; 7.5 QUOTIENT LATTICE; 7.6 LATTICE HOMOMORPHISM AND CONGRUENCE; 7.7 PROPERTIES OF LATTICE CONGRUENCE BLOCKS; 7.8 APPLICATION: MODEL CHECKING ON REDUCED LATTICES; 7.9 PROBLEMS; 7.10 BIBLIOGRAPHIC REMARKS; Chapter 8: Modular Lattices; 8.1 INTRODUCTION; 8.2 MODULAR LATTICE; 8.3 CHARACTERIZATION OF MODULAR LATTICES; 8.4 PROBLEMS; 8.5 BIBLIOGRAPHIC REMARKS; Chapter 9: Distributive Lattices; 9.1 INTRODUCTION.
- 3.10 A Lower Bound on Online Chain Partition3.11 Problems; 3.12 Bibliographic Remarks; Chapter 4: Merging Algorithms; 4.1 Introduction; 4.2 Algorithm to Merge Chains in Vector Clock Representation; 4.3 An Upper Bound for Detecting an Antichain of Size; 4.4 A Lower Bound for Detecting an Antichain of Size; 4.5 An Incremental Algorithm for Optimal Chain Decomposition; 4.6 Problems; 4.7 Bibliographic Remarks; Chapter 5: Lattices; 5.1 Introduction; 5.2 Sublattices; 5.3 Lattices as Algebraic Structures; 5.4 Bounding The Size of The Cover Relation of a Lattice
- Cover; Table of Contents; Title Page; Copyright; Dedication; List Of Figures; Nomenclature; Preface; Chapter 1: Introduction; 1.1 Introduction; 1.2 Relations; 1.3 Partial Orders; 1.4 Join and Meet Operations; 1.5 Operations on Posets; 1.6 Ideals and Filters; 1.7 Special Elements in Posets; 1.8 Irreducible Elements; 1.9 Dissector Elements; 1.10 Applications: Distributed Computations; 1.11 Applications: Combinatorics; 1.12 Notation and Proof Format; 1.13 Problems; 1.14 Bibliographic Remarks; Chapter 2: Representing Posets; 2.1 Introduction; 2.2 Labeling Elements of The Poset