Principles and Practice of Constraint Programming – CP 2000: 6th International Conference, CP 2000 Singapore, September 18–21, 2000 Proceedings

Alan K. Mackworth (auth.), Rina Dechter (eds.)3540410538, 9783540410539

This volume constitutes the refereed proceedings of the 6th International Conference on Principles and Practice of Constraint Programming, CP 2000, held in Singapore in September 2000. The 31 revised full papers and 13 posters presented together with three invited contributions were carefully reviewed and selected from 101 submissions. All current issues of constraint processing, ranging from theoretical and foundational issues to applications in various fields are addressed.

---

Table of contents :
Constraint-Based Agents: The ABC’s of CBA’s….Pages 1-10
Constraints for Interactive Graphical Applications….Pages 11-12
Meta-complexity Theorems: Talk Abstract….Pages 13-17
Automatic Generation of Propagation Rules for Finite Domains….Pages 18-34
Extending Forward Checking….Pages 35-51
Global Constraints as Graph Properties on a Structured Network of Elementary Constraints of the Same Type….Pages 52-66
Universally Quantified Interval Constraints….Pages 67-82
Constraint Propagation for Soft Constraints: Generalization and Termination Conditions….Pages 83-97
Constraints Inference Channels and Secure Databases….Pages 98-113
Refinements and Independence: A Simple Method for Identifying Tractable Disjunctive Constraints….Pages 114-127
A Language for Audiovisual Template Specification and Recognition….Pages 128-142
Random 3-SAT: The Plot Thickens….Pages 143-159
New Tractable Classes from Old….Pages 160-171
Expressiveness of Full First Order Constraints in the Algebra of Finite or Infinite Trees….Pages 172-186
Cutting Planes in Constraint Programming: An Hybrid Approach….Pages 187-201
A Constraint-Based Framework for Prototyping Distributed Virtual Applications….Pages 202-218
A Scalable Linear Constraint Solver for User Interface Construction….Pages 218-233
A Constraint Programming Approach for Solving Rigid Geometric Systems….Pages 233-248
Maintaining Arc-Consistency within Dynamic Backtracking….Pages 249-261
New Search Heuristics for Max-CSP….Pages 262-277
Analysis of Random Noise and Random Walk Algorithms for Satisfiability Testing….Pages 278-290
Boosting Search with Variable Elimination….Pages 291-305
Faster Algorithms for Bound-Consistency of the Sortedness and the Alldifferent Constraint….Pages 306-319
Practical Investigation of Constraints with Graph Views….Pages 320-336
A Hybrid Search Architecture Applied to Hard Random 3-SAT and Low-Autocorrelation Binary Sequences….Pages 337-352
Singleton Consistencies….Pages 353-368
Linear Formulation of Constraint Programming Models and Hybrid Solvers….Pages 369-383
A Global Constraint Combining a Sum Constraint and Difference Constraints….Pages 384-395
Efficient Querying of Periodic Spatiotemporal Objects….Pages 396-410
Arc Consistency for Soft Constraints….Pages 411-425
Optimal Anytime Constrained Simulated Annealing for Constrained Global Optimization….Pages 425-440
SAT v CSP….Pages 441-456
Instruction Scheduling with Timing Constraints on a Single RISC Processor with 0/1 Latencies….Pages 457-469
Arc Consistency on n -ary Monotonic and Linear Constraints….Pages 470-483
Some Observations on Durations, Scheduling and Allen’s Algebra….Pages 484-489
Using Randomization and Learning to Solve Hard Real-World Instances of Satisfiability….Pages 489-494
Finding Minimal Unsatisfiable Subformulae in Satisfiability Instances….Pages 495-499
Branching Constraint Satisfaction Problems for Solutions Robust under Likely Changes….Pages 500-504
Constraint Propagation: Between Abstract Models and ad hoc Strategies….Pages 505-509
How to Model and Verify Concurrent Algorithms for Distributed CSPs….Pages 510-514
The Phase Transition in Distributed Constraint Satisfaction Problems: First Results….Pages 515-519
Cooperating Constraint Solvers….Pages 520-525
An Empirical Study of Probabilistic Arc Consistency as a Variable Ordering Heuristic….Pages 525-530
On Dual Encodings for Non-binary Constraint Satisfaction Problems….Pages 531-536
Algebraic Simplification Techniques for Propositional Satisfiability….Pages 537-542
An Original Constraint Based Approach for Solving over Constrained Problems….Pages 543-548
An Efficient Approximate Algorithm for Winner Determination in Combinatorial Auctions….Pages 549-553