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

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