Abstract
Ce rapport offre un panorama de nos recherches récentes sur l'intérêt des formes compilées pour la manipulation de contraintes ou de formules logiques et plus généralement de contraintes flexibles exprimant des préférences et/ou des incertitudes. Nous nous interressons en particulier aux formes de type diagrammes de décision et en proposons plusieurs extensions: les diagrammes de décision valués qui permettent de mémoriser non seulement un ensemble de solutions mais aussi les préférences de l'utilisateur sur ces solutions (ce type de structure a été utilisé dans le cadre de problèmes de configuration interactive). Les "automates d'arbres" qui permettent une meilleure exploitation de la structure du problème et en particulier des indépendances conditionnelles, et donc offrent une forme compilée plus compacte. Les "graphes de décision" reformulent les principes des automates d'arbres dans le cadre général des DNNF (formes normales négatives décomposables), ce qui permet de détecter tout un ensemble de classes traitables pour des problèmes classiques comme l'élimination de variable par un quantificateur, le comptage de modèles, l'équivalence de formules. Enfin, nous introduisons les NNF (décomposables ou non) valuées qui élargissent la carte des formes compilées NNF à la représentation de toute fonction dans un ensemble (partiellement) ordonné.