Foundations of Constraint Satisfaction

Research Monograph

Constraint satisfaction is a decision problem that involves finite choices. It is ubiquitous. The goal is to find values for a set of variables that will satisfy a given set of constraints. It is the core of many applications in artificial intelligence, and has found its application in many areas, such as planning and scheduling. Because of its generality, most AI researchers should be able to benefit from having good knowledge of techniques in this field.

Published in 1993, this book was the first attempt to define the scope of constraint satisfaction. It covers both the theoretical and the implementation aspects of the subject. It provides a framework for studying this field, relates different research, and resolves ambiguity in a number of concepts and algorithms in the literature.

This book is arguably the most rigorous book in the field. All major concepts were defined in First Order Predicate Calculus (FOPC). Concepts defined this way are precise and unambiguous.

This book was published by Academic Press:

Tsang, E.P.K.,
Foundations of Constraint Satisfaction,
Academic Press, London and San Diego, 1993
ISBN 0-12-701610-4

It is now out of print.

Reprint (with minor corrections*) is available from 2014.05.13:

Tsang, E.P.K.,
Foundations of Constraint Satisfaction,
Edited by Thom Fruehwirth, Books on Demand, 2014
ISBN 978-3735723666
* About this version:
Minor editorial errors in the 1993 version have been corrected.