*********************************************************************
*                       Ecole Normale Supe'rieure                   *
*                                                                   *
*                              Se'minaire                           *
*                SEMANTIQUE ET INTERPRETATION ABSTRAITE             *
*                              P. Cousot                            *
*   ENS, Equipe-projet INRIA "Abstraction" commune avec ENS & CNRS  *
*                                                                   *
*                        Vendredi, 14h00--16h00                     *
*                         Salle U/V, niveau -2                      *
*                  DI  ENS  45 rue d'Ulm  75005 Paris               *
*********************************************************************

***  Vendredi 19 Novembre 2010, 14h00-15h00 *************************

Domaines abstraits en programmation par contraintes

Charlotte Truchet et Marie  Pelleau (Universit'e de Nantes)

Re'sume'/ Abstract:

La programmation par contraintes (PPC) est un paradigme de programmation
déclaratif, efficace pour résoudre des problèmes fortement
combinatoires. Plusieurs méthodes de résolution existent, mais elles
diffèrent significativement selon que le problème est en variables
entières ou réelles, au point que la résolution de problèmes mixtes
(discrets et continus) n'est possible qu'à travers des artifices.  Au
contraire, avec les domaines abstraits, l'interprétation abstraite sait
bien traiter différents types de variables, et les fondements théoriques
sous-jacents (approximations extérieures, points fixes) sont assez
proches des définitions de consistances utilisées en PPC. L'idée
d'adapter les domaines abstraits aux contraintes semble donc naturelle. 
En fait, les domaines abstraits adaptés aux contraintes sont
sensiblement plus simples qu'en interprétation abstraite.  Ils apportent
cependant deux nouveautés à la PPC : d'abord, la définition d'une
consistance abstraite, indépendante du type des variables sous-jacentes,
ensuite, la possibilité de définir des domaines relationnels, alors que
toutes les consistances en PPC portent sur des produits cartésiens de
domaines.

Lors de ce séminaire nous présenterons d'abord une brève introduction à
la programmation par contraintes, puis la notion de consistance
abstraite définie à partir de domaines abstraits pour les contraintes. 
Enfin, nous montrerons un exemple d'utilisation en PPC d'un domaine
relationnel, les octogones, puis nous évoquerons un travail en cours sur
la résolution de contraintes mixtes.

*********************************************************************
Pour recevoir l'annonce par courrier electronique:
WWW: http://www.di.ens.fr/~cousot/annonceseminaire.shtml
*********************************************************************