lindsvedotnet

Interesting papers related to my thesis work (This is mostly for my own reference):

Christian Schulte: «Programming Constraint Services»:

This thesis presents design, application, implementation, and evaluation of computation spaces as abstractions for programming constraint services at a high level. Spaces are seamlessly integrated into a concurrent programming language and make constraint-based computations compatible with concurrency through encapsulation. Spaces are applied to search and combinators as essential constraint services. State-of-the-art and new search engines such as visual interactive search and parallel search are covered. Search is expressive and concurrency-compatible by using copying rather than trailing. Search is space and time efficient by using recomputation. Composable combinators, also known as deep-guard combinators, stress the control facilities and concurrency integration of spaces. The implementation of spaces comes as an orthogonal extension to the implementation of the underlying programming language. The resulting implementation is shown to be competitive with existing constraint programming systems.

Christian Schulte: «Views and Iterators for Generic Constraint Implementations»:

This paper introduces an architecture for generic constraint implementations based on variable views and range iterators. Views allow, for example, to scale, translate, and negate variables. The paper shows how to make constraint implementations generic and how to reuse a single generic implementation with different views for different constraints. Applications of views exemplify their usefulness and their potential for simplifying constraint implementations. We introduce domain operations compatible with views based on range iterators. The paper evaluates different implementation techniques for the presented architecture.

Christian Schulte: «Speeding Up Constraint Propagation»:

This paper presents a model and implementation techniques for speeding up constraint propagation. Two fundamental approaches to improving constraint propagation are explored: keeping track of which propagators are at fixpoint, and choosing which propagator to apply next. We show how idempotence reasoning and events help track fixpoints more accurately. We improve these methods by using them dynamically (taking into account current domains to improve accuracy). We define priority-based approaches to choosing a next propagator and show that dynamic priorities can improve propagation. We illustrate that the use of multiple propagators for the same constraint can be advantageous with priorities, and introduce staged propagators which combine the effects of multiple propagators with priorities for greater efficiency.

Jean-Xavier Rampon, et.al: «Global Constraint Catalog» (direct link to pdf)

This report presents a catalog of global constraints where each constraint is explicitly described in terms of graph properties and/or automata. When available, it also presents some typical usage as well as some pointers to existing filtering algorithms.