Compiling CSPs into Tree-Driven Automata for Interactive Solving

Abstract : Constraint programming techniques are widely used to model and solve decision problems and many algorithms have been developed to solve automatically and efficiently families of CSPs; nevertheless, they do not help solve interactive decision support problems, like product configuration. In such problems, the user chooses the values of the variables, and the role of the system is not to solve the CSP, but to help the user in this task. Dynamic global consistency maintaining is one of the most useful functionalities that should be offered by such a CSP platform. Unfortunately, this task is intractable in the worst case. Since interactivity requires short response times, intractability must be circumvented some way. To this end, compilation methods have been proposed that transform the original problem into a data structure allowing a short response time. In this paper, we extend the work of Amilhastre et al. [1] and Vempaty [15] by the use of a new structure, tree-driven automata, that takes advantage of the structural characteristics of configuration problems (decomposition of the components into independent subcomponents). Tree-driven automata can be far more compact than classical automata while keeping their good properties, especially a tractable complexity for the maintenance of global consistency.
Type de document :
Communication dans un congrès
Barry 0'Sullivan; Eugene C. Freuder. User-Interaction in Constraint Satisfaction, Sep 2003, Kinsale, County Cork, Ireland. 3rd International Workshop on User-Interaction in Constraint Satisfaction Held in conjunction with 9th International Conference on Principles and Practice of Constraint Programming, 2003, 〈http://www.cs.ucc.ie/~osullb/UICS-03/〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00269625
Contributeur : Christine Carvalho de Matos <>
Soumis le : jeudi 3 avril 2008 - 08:22:02
Dernière modification le : jeudi 11 janvier 2018 - 06:26:54

Identifiants

  • HAL Id : lirmm-00269625, version 1

Citation

Hélène Fargier, Marie-Catherine Vilarem. Compiling CSPs into Tree-Driven Automata for Interactive Solving. Barry 0'Sullivan; Eugene C. Freuder. User-Interaction in Constraint Satisfaction, Sep 2003, Kinsale, County Cork, Ireland. 3rd International Workshop on User-Interaction in Constraint Satisfaction Held in conjunction with 9th International Conference on Principles and Practice of Constraint Programming, 2003, 〈http://www.cs.ucc.ie/~osullb/UICS-03/〉. 〈lirmm-00269625〉

Partager

Métriques

Consultations de la notice

45