This book constitutes the thoroughly refereed and extended post-workshop proceedings of the 12th Annual ERCIM International Workshop on Constraint Solving and Constraint Logic Programming, CSCLP 2007, held in Rocquencourt, France, in June 2007.
The 10 revised full papers presented were carefully reviewed and selected from 16 initial submissions. The papers address all aspects of constraint and logic programming, including foundational issues, implementation techniques, new applications as well as teaching issues. Particular emphasis is placed on assessing the current state of the art and identifying future directions.
Author(s): François Fages, Francesca Rossi, Sylvain Soliman
Series: Lecture Notes in Artificial Intelligence 5129
Edition: 1
Publisher: Springer
Year: 2008
Language: English
Pages: 164
Front matter......Page 1
Introduction......Page 7
Soft Constraints......Page 9
Strategic Games......Page 11
Optimality in SCSPs and Nash Equilibria in Graphical Games......Page 12
From SCSPs to Graphical Games: A Local Mapping......Page 13
From SCSPs to Graphical Games: A Global Mapping......Page 16
Optimality in SCSPs and Pareto Efficient Joint Strategies in Graphical Games......Page 17
From SCSPs to Graphical Games......Page 18
From Graphical Games to SCSPs......Page 19
Conclusions......Page 21
References......Page 22
Introduction......Page 23
Motivation and Background......Page 24
Temporal Networks with Alternatives......Page 25
Temporal Constraints......Page 29
References......Page 36
Introduction......Page 38
Background......Page 40
From Trust Networks to $and-or$ Graph......Page 43
$and-or$ Graphs Using SCLP......Page 46
An Implementation of the Model......Page 48
Complexity Considerations......Page 49
Conclusions......Page 50
References......Page 51
Introduction......Page 53
Preliminaries......Page 54
The Asynchronous Backtracking Algorithm......Page 55
The $ABT_{hyb}$ Algorithm......Page 56
Correctness, Completeness and Termination......Page 57
Comparison with $ABT$......Page 60
Distributed $n$-Queens......Page 63
Random Problems......Page 64
Distributed Sensor-Mobile Problems......Page 65
Conclusions......Page 66
References......Page 67
Introduction......Page 68
Notation and Background......Page 69
Singleton Consistencies......Page 70
Pruning Decisions......Page 71
Experimental Results......Page 73
Graph Coloring......Page 74
Random CSPs......Page 75
Partial Latin Squares......Page 77
Discussion......Page 78
Conclusion......Page 79
References......Page 80
Introduction......Page 82
CP(Graph)......Page 83
CP(Map)......Page 84
Implementing Map Variables in a Finite Domain Solver......Page 85
Additional Constraints and Propagators......Page 86
A Global Constraint Based on Matching Theory......Page 87
Approximate Graph Matching and Other Matching Problems......Page 88
Optional Nodes and Forbidden Arcs......Page 90
Experimental Results......Page 92
Conclusion......Page 93
References......Page 94
Introduction......Page 97
Constraint Handling Rules (CHR)......Page 98
Implementing Union-Find in CHR......Page 100
Optimised Union-Find......Page 101
Generalised Union-Find......Page 102
Complexity......Page 104
Correctness......Page 107
Instance of Boolean Equations......Page 109
Instance of Linear Polynomials......Page 111
Conclusions......Page 112
References......Page 113
Introduction......Page 115
Constraints......Page 118
Criteria and Preferences......Page 119
Wishes......Page 120
Atomic Optimization Step......Page 121
Alternative Optimizations......Page 123
Lexicographical Approach......Page 124
Alternative Sequentializations......Page 126
Importance Preferences......Page 127
Trade-Offs and Preference Limits......Page 128
Conclusion......Page 131
References......Page 132
Introduction......Page 133
Background......Page 134
The TFOS Model......Page 135
GCC and Value-Disjoint among Constraints......Page 138
GCC and Variable-Disjoint among Constraints......Page 139
Towards a Propagation Algorithm for TFOS......Page 140
The Weighted TFOS Problem......Page 141
Three Families of Sets Cause NP-Hardness......Page 142
Modelling Intractable Problems Using the TFOS Model......Page 143
Conclusion......Page 144
A Intermediate Proofs from Observation 1 to Theorem 1......Page 145
Introduction......Page 148
Motivation by AI Problems......Page 149
Mutual Exclusion Network and Related Problem......Page 151
Global Filtration for Goal Satisfaction in Mutex Network......Page 153
Formal Definition of Projection Consistency......Page 154
Random Goal Satisfaction Problems......Page 156
Problems Arising in Concurrent Planning......Page 160
Note on Additional Related Works and Conclusion......Page 161
References......Page 162
Back matter......Page 164
