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

Chapter 1 Introduction
Chapter 2 Representing Posets
Chapter 3 Dilworth’s Theorem
Chapter 4 Merging Algorithms
Chapter 5 Lattices
Chapter 6 Lattice Completion
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
Chapter 15 Lattice of Maximal Antichains
Chapter 16 Dimension Theory
Chapter 17 Fixed Point Theory