O'Reilly logo

Introduction to Lattice Theory with Computer Science Applications by Vijay K. Garg

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 c01-math-0001 over any set is a subset of . For example, let

Then, one possible relation ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required