Home Page Icon
Home Page
Table of Contents for
Cover
Close
Cover
by Vijay K. Garg
Introduction to Lattice Theory with Computer Science Applications
Cover
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
2.3 Adjacency List Representation
2.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
3.10 A Lower Bound on Online Chain Partition
3.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
5.5 Join-Irreducible Elements Revisited
5.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–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 MINING
6.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
9.2 FORBIDDEN SUBLATTICES
9.3 JOIN-PRIME ELEMENTS
9.4 BIRKHOFF'S REPRESENTATION THEOREM
9.5 FINITARY DISTRIBUTIVE LATTICES
9.6 PROBLEMS
9.7 BIBLIOGRAPHIC REMARKS
Chapter 10: Slicing
10.1 Introduction
10.2 Representing Finite Distributive Lattices
10.3 Predicates on Ideals
10.4 Application: Slicing Distributed Computations
10.5 Problems
10.6 Bibliographic Remarks
Chapter 11: Applications of Slicing to Combinatorics
11.1 Introduction
11.2 Counting Ideals
11.3 Boolean Algebra and Set Families
11.4 Set Families of Size
11.5 Integer Partitions
11.6 Permutations
11.7 Problems
11.8 Bibliographic Remarks
Chapter 12: Interval Orders
12.1 Introduction
12.2 Weak Order
12.3 Semiorder
12.4 Interval Order
12.5 Problems
12.6 Bibliographic Remarks
Chapter 13: Tractable posets
13.1 Introduction
13.2 Series–Parallel Posets
13.3 Two-Dimensional Posets
13.4 Counting Ideals of A Two-Dimensional Poset
13.5 Problems
13.6 Bibliographic Remarks
Chapter 14: Enumeration Algorithms
14.1 Introduction
14.2 BFS Traversal
14.3 DFS Traversal
14.4 Lex Traversal
14.5 Uniflow Partition of Posets
14.6 Enumerating Tuples of Product Spaces
14.7 Enumerating all Subsets
14.8 Enumerating all Subsets of Size
14.9 Enumerating Young'S Lattice
14.10 Enumerating Permutations
14.11 Lexical Enumeration of all Order Ideals of A Given Rank
14.12 Problems
14.13 Bibliographic Remarks
Chapter 15: Lattice of Maximal Antichains
15.1 Introduction
15.2 Maximal Antichain Lattice
15.3 An Incremental Algorithm Based on Union Closure
15.4 An Incremental Algorithm Based on BFS
15.5 Traversal of The Lattice of Maximal Antichains
15.6 Application: Detecting Antichain-Consistent Predicates
15.7 Construction and Enumeration of Width Antichain Lattice
15.8 Lexical Enumeration of Closed Sets
15.9 Construction of Lattices Based on Union Closure
15.10 Problems
15.11 Bibliographic Remarks
Chapter 16: Dimension Theory
16.1 Introduction
16.2 Chain Realizers
16.3 Standard Examples of Dimension Theory
16.4 Relationship Between The Dimension and The Width of A Poset
16.5 Removal Theorems for Dimension
16.6 Critical Pairs in The Poset
16.7 String Realizers
16.8 Rectangle Realizers
16.9 Order Decomposition Method and Its Applications
16.10 Problems
16.11 Bibliographic Remarks
Chapter 17: Fixed Point Theory
17.1 Complete Partial Orders
17.2 Knaster–Tarski Theorem
17.3 Application: Defining Recursion Using Fixed Points
17.4 Problems
17.5 Bibliographic Remarks
Bibliography
Index
End User License Agreement
Search in book...
Toggle Font Controls
Playlists
Add To
Create new playlist
Name your new playlist
Playlist description (optional)
Cancel
Create playlist
Sign In
Email address
Password
Forgot Password?
Create account
Login
or
Continue with Facebook
Continue with Google
Sign Up
Full Name
Email address
Confirm Email Address
Password
Login
Create account
or
Continue with Facebook
Continue with Google
Next
Next Chapter
Contents
Add Highlight
No Comment
..................Content has been hidden....................
You can't read the all page of ebook, please click
here
login for view all page.
Day Mode
Cloud Mode
Night Mode
Reset