Introduction to Lattice Theory with Computer Science Applications

Preface

As many books exist on lattice theory, I must justify writing another book on the subject. This book is written from the perspective of a computer scientist rather than a mathematician. In many instances, a mathematician may be satisfied with a nonconstructive existential proof, but a computer scientist is interested not only in construction but also in the computational complexity of the construction. I have attempted to give “algorithmic” proofs of theorems whenever possible.

This book is also written for the sake of students rather than a practicing mathematician. In many instances, a student needs to learn the heuristics that guide the proof, besides the proof itself. It is not sufficient just to learn an important theorem. One must also learn ways to extend and analyze a theorem. I have also made an effort to include exercises with each chapter. A mathematical subject can only be learned by solving problems related to that subject.

I would like to thank the students at the University of Texas at Austin, who took my course on lattice theory. I also thank my co-authors for various papers related to lattice theory and applications in distributed computing: Anurag Agarwal, Arindam Chakraborty, Yen-Jung Chang, Craig Chase, Himanshu Chauhan, Selma Ikiz, Ratnesh Kumar, Neeraj Mittal, Sujatha Kashyap, Vinit Ogale, Alper Sen, Alexander Tomlinson, and Brian Waldecker. I owe special thanks to Bharath Balasubramanina, Vinit Ogale, Omer Shakil, Alper Sen, and Roopsha Samanta who ...