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

Front Cover
Rina Dechter
Springer Science & Business Media, Sep 6, 2000 - Computers - 564 pages
As computer science enters the new millennium, methods and languages for reasoning with constraints have come to play an important role, with both t- oretical advances and practical applications. Constraints have emerged as the basis of a representational and computational paradigm that draws from many disciplinesandcanbebroughttobearonmanyproblemdomains, includingar- ?cial intelligence, databases, and combinatorial optimization. The conference is concerned with all aspects of computing with constraints including algorithms, applications, environments, languages, models and systems. The Sixth InternationalConference on Principles and Practiceof Constraint Programming (CP2000) continues to provide an international forum for p- senting and discussing state-of-the-art research and applications involving c- straints.Afterafewannualworkshops, CP'95tookplaceinCassis, France;CP'96 in Cambridge, USA; CP'97 in Schloss Hagenberg, Austria; CP'98 in Pisa, Italy and CP'99 in Alexandria, USA. This year the conference is held in Singapore, from 18 through 21 September 2000. This volume comprises the papers that were accepted for presentation at CP2000.From the 101 papersthat were submitted, 31 papers wereaccepted for presentation in the plenary session and 13 papers were selected as posters and have a short version (?ve pages) in this volume. All papers were subjected to rigorous review three program committee members (or their designated revi- ers) refereed each paper. Decisions were reached following discussions among reviewers and, in some instances, by e-mail consultation of the entire program committee.Ibelievethereaderwill?ndthesearticlestobeofthehighestquality, representing a signi?cant contribution to the ?eld.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

The ABCs of CBAs
1
Constraints for Interactive Graphical Applications
11
Talk Abstract
13
Automatic Generation of Propagation Rules for Finite Domains
18
Extending Forward Checking
35
Global Constraints as Graph Properties on a Structured Network of Elementary Constraints of the Same Type
52
Universally Quantified Interval Constraints
67
Generalization and Termination Conditions
83
Singleton Consistencies
353
Linear Formulation of Constraint Programming Models and Hybrid Solvers
369
A Global Constraint Combining a Sum Constraint and Difference Constraints
384
Efficient Querying of Periodic Spatiotemporal Objects
396
Arc Consistency for Soft Constraints
411
Optimal Anytime Constrained Simulated Annealing for Constrained Global Optimization
425
SAT v CSP
441
Instruction Scheduling with Timing Constraints on a Single RISC Processor with 01 Latencies
457

Constraints Inference Channels and Secure Databases
98
A Simple Method for Identifying Tractable Disjunctive Constraints
114
A Language for Audiovisual Template Specification and Recognition
128
The Plot Thickens
143
New Tractable Classes from Old
160
Expressiveness of Full First Order Constraints in the Algebra of Finite or Infinite Trees
172
An Hybrid Approach
187
A ConstraintBased Framework for Prototyping Distributed Virtual Applications
202
A Scalable Linear Constraint Solver for User Interface Construction
218
A Constraint Programming Approach for Solving Rigid Geometric Systems
233
Maintaining ArcConsistency within Dynamic Backtracking
249
New Search Heuristics for MaxCSP
262
Analysis of Random Noise and Random Walk Algorithms for Satisfiability Testing
278
Boosting Search with Variable Elimination
291
Faster Algorithms for BoundConsistency of the Sortedness and the Alldifferent Constraint
306
Practical Investigation of Constraints with Graph Views
320
A Hybrid Search Architecture Applied to Hard Random 3SAT and LowAutocorrelation Binary Sequences
337
Arc Consistency on nary Monotonic and Linear Constraints
470
Some Observations on Durations Scheduling and Allens Algebra
484
Using Randomization and Learning to Solve Hard RealWorld Instances of Satisfiability
489
Finding Minimal Unsatisfiable Subformulae in Satisfiability Instances
495
Branching Constraint Satisfaction Problems for Solutions Robust under Likely Changes
500
Between Abstract Models and ad hoc Strategies
505
How to Model and Verify Concurrent Algorithms for Distributed CSPs
510
First Results
515
Cooperating Constraint Solvers
520
An Empirical Study of Probabilistic Arc Consistency as a Variable Ordering Heuristic
525
On Dual Encodings for Nonbinary Constraint Satisfaction Problems
531
Algebraic Simplification Techniques for Propositional Satisfiability
537
An Original Constraint Based Approach for Solving over Constrained Problems
543
An Efficient Approximate Algorithm for Winner Determination in Combinatorial Auctions
549
Author Index
554
Copyright

Other editions - View all

Common terms and phrases

Bibliographic information