Constraint processing / Rina Dechter ; with contributions by David Cohen, Peter Jeavons, Francesca Rossi.

Format:

Book

Author/Creator:

Dechter, Rina, 1950-

Series:

Morgan Kaufmann Series in Artificial Intelligence

The Morgan Kaufmann Series in Artificial Intelligence

Language:

English

Subjects (All):

Constraint programming (Computer science).

Physical Description:

1 online resource (503 p.)

Edition:

1st edition

Place of Publication:

San Francisco : Morgan Kaufmann Publishers, c2003.

Language Note:

English

System Details:

text file

Summary:

Constraint satisfaction is a simple but powerful tool. Constraints identify the impossible and reduce the realm of possibilities to effectively focus on the possible, allowing for a natural declarative formulation of what must be satisfied, without expressing how. The field of constraint reasoning has matured over the last three decades with contributions from a diverse community of researchers in artificial intelligence, databases and programming languages, operations research, management science, and applied mathematics. Today, constraint problems are used to model cognitive tasks in vision,

Contents:

Front Cover; Constraint Processing; Copyright Page; Foreword; Contents; Preface; Chapter 1. Introduction; 1.1 Basic Concepts and Examples; 1.2 Overview by Chapter; 1.3 Mathematical Background; 1.4 Bibliographical Notes; 1.5 Exercises; Part I: Basics of Constraint Processing; Chapter 2. Constraint Networks; 2.1 Constraint Networks and Constraint Satisfaction; 2.2 Numeric and Boolean Constraints; 2.3 Properties of Binary Constraint Networks; 2.4 Summary; 2.5 Bibliographical Notes; 2.6 Exercises; Chapter 3. Consistency-Enforcing and Constraint Propagation; 3.1 Why Propagate Constraints?

3.2 Arc-Consistency3.3 Path-Consistency; 3.4 Higher Levels of i-Consistency; 3.5 Arc-Consistency for Nonbinary Constraints; 3.6 Constraint Propagation for Numeric and Boolean Constraints; 3.7 Trees, Bivalued Networks, and Horn Theories; 3.8 Summary; 3.9 Bibliographical Notes; 3.10 Exercises; Chapter 4. Directional Consistency; 4.1 Graph Concepts: Induced Width; 4.2 Directional Local Consistency; 4.3 Width versus Local Consistency; 4.4 Adaptive Consistency and Bucket Elimination; 4.5 Summary; 4.6 Bibliographical Notes; 4.7 Exercises; Chapter 5. General Search Strategies: Look-Ahead

5.1 The State Space Search5.2 Backtracking; 5.3 Look-Ahead Strategies; 5.4 Satisfiability: Look-Ahead in Backtracking; 5.5 Summary; 5.6 Bibliographical Notes; 5.7 Exercises; Chapter 6. General Search Strategies: Look-Back; 6.1 Conflict Sets; 6.2 Backjumping Styles; 6.3 Complexity of Backjumping; 6.4 Learning Algorithms; 6.5 Look-Back Techniques for Satisfiability; 6.6 Integration and Comparison of Algorithms; 6.7 Summary; 6.8 Bibliographical Notes; 6.9 Exercises; Chapter 7. Stochastic Greedy Local Search; 7.1 Greedy Local Search; 7.2 Random Walk Strategies

7.3 Hybrids of Local Search and Inference7.4 Summary; 7.5 Bibliographical Notes; 7.6 Exercises; Part II: Advanced Methods; Chapter 8. Advanced Consistency Methods; 8.1 Relational Consistency; 8.2 Directional Consistency Revisited; 8.3 Domain and Constraint Tightness; 8.4 Inference for Boolean Theories; 8.5 Row-Convex Constraints; 8.6 Linear Inequalities; 8.7 Summary; 8.8 Bibliographical Notes; 8.9 Exercises; Chapter 9. Tree Decomposition Methods; 9.1 Acyclic Networks; 9.2 Tree-Based Clustering; 9.3 ADAPTIVE-CONSISTENCY as Tree Decomposition; 9.4 Summary; 9.5 Bibliographical Notes

9.6 ExercisesChapter 10. Hybrids of Search and Inference: Time-Space Trade-Offs; 10.1 Specialized Cutset Schemes; 10.2 Hybrids: Conditioning First; 10.3 Hybrids: Inference First; 10.4 A Case Study of Combinatorial Circuits; 10.5 Summary; 10.6 Bibliographical Notes; 10.7 Exercises; Chapter 11. Tractable Constraint Languages; 11.1 The CSP Search Problem; 11.2 Constraint Languages; 11.3 Expressiveness of Constraint Languages; 11.4 Complexity of Constraint Languages; 11.5 Hybrid Tractability; 11.6 Summary; 11.7 Bibliographical Notes; 11.8 Exercises; Chapter 12. Temporal Constraint Networks

12.1 Qualitative Networks

Notes:

Description based upon print version of record.

Includes bibliographical references (p. [441]-458) and index.

ISBN:

9786611072957

9781281072955

1281072958

9780080502953

0080502954

OCLC:

228143692