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

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
 Chapter 5: Lattices

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 MINING
 6.13 PROBLEMS
 6.14 BIBLIOGRAPHIC REMARKS
 Chapter 7: Morphisms
 Chapter 8: Modular Lattices
 Chapter 9: Distributive Lattices
 Chapter 10: Slicing
 Chapter 11: Applications of Slicing to Combinatorics
 Chapter 12: Interval Orders
 Chapter 13: Tractable posets

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 AntichainConsistent 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
 Bibliography
 Index
 End User License Agreement
Product information
 Title: Introduction to Lattice Theory with Computer Science Applications
 Author(s):
 Release date: May 2015
 Publisher(s): Wiley
 ISBN: 9781118914373
You might also like
book
40 Algorithms Every Programmer Should Know
Learn algorithms for solving classic computer science problems with this concise guide covering everything from fundamental …
book
Discrete Structures, Logic, and Computability, 4th Edition
Following the recent updates to the 2013 ACM/IEEE Computer Science curricula, Discrete Structures, Logic, and Computability, …
book
Essential Algorithms, 2nd Edition
A friendly introduction to the most useful algorithms written in simple, intuitive English The revised and …
book
Head First Design Patterns, 2nd Edition
You know you don’t want to reinvent the wheel, so you look to design patterns—the lessons …