## Principles and Practice of Constraint Programming - CP 2000: 6th International Conference, CP 2000 Singapore, September 18-21, 2000 ProceedingsAs 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 |

554 | |

### Other editions - View all

Principles and Practice of Constraint Programming - CP 2000: 6th ... Rina Dechter Limited preview - 2003 |

Principles and Practice of Constraint Programming - CP 2000: 6th ... Rina Dechter No preview available - 2000 |

### Common terms and phrases

algebra applied approach arc consistency arity Artificial Intelligence backtracking Berlin Heidelberg 2000 branching clause complexity components consider constraint graph Constraint Programming constraint propagation constraint satisfaction problems constraint solver constraint system corresponding CPLEX database Dechter defined Definition denote density domain dual encoding edge elimination enforcing arc-consistency example feasible schedule finite formulation forward checking framework function given global constraints Golomb ruler heuristic HiRise hybrid idempotent implementation inequalities instantiation integer interval iteration linear LNCS Logic Programming lower bound LU decomposition Max-CSP median running method Mini-Bucket n-ary node non-binary number of variables operation optimal paper partial order path-consistency performance polynomial Proc Proof pruning query random relations relaxation satisfiability search algorithm search space search tree Section semiring sequence SGAC singleton solution solving straint strongly connected components techniques template temporal Theorem tractable tuple unit propagation