Introduction to Lattice Theory with Computer Science Applications

Chapter 1Introduction

1.1 Introduction

Partial order and lattice theory play an important role in many disciplines of computer science and engineering. For example, they have applications in distributed computing (vector clocks and global predicate detection), concurrency theory (pomsets and occurrence nets), programming language semantics (fixed-point semantics), and data mining (concept analysis). They are also useful in other disciplines of mathematics such as combinatorics, number theory, and group theory.

This book differs from earlier books written on the subject in two aspects. First, this book takes a computational perspective—the emphasis is on algorithms and their complexity. While mathematicians generally identify necessary and sufficient conditions to characterize a property, this book focuses on efficient algorithms to test the property. As a result of this bias, much of the book concerns itself only with finite sets. Second, existing books do not dwell on applications of lattice theory. This book treats applications at par with the theory. In particular, I have given applications of lattice theory to distributed computing and combinatorics.

This chapter covers the basic definitions of partial orders.

1.2 Relations

A partial order is simply a relation with certain properties. A relation over any set is a subset of . For example, let

Then, one possible relation ...