Abstract FR:

L'utilisation des problemes de satisfaction de contraintes (csp) dans certaines applications a mis en evidence la necessite d'etendre aussi bien le formalisme que le champ des questions traitees. Le calcul et la representation de l'ensemble des solutions est une reponse possible a ces nouveaux besoins. Nous proposons une representation par automates d'etats finis (fa) non deterministes qui generalise la representation par fa deterministes due a vempaty. Nous nous interessons a la minimisation des fa non deterministes, probleme qui reste np-difficile sur la classe des langages associes aux ensembles de solutions de csp : langages finis composes de mots de meme longueur. Nous etudions le probleme de recouvrement minimum par bicliques de graphes bipartis qui est equivalent au probleme de minimisation de fa reconnaissant uniquement des mots de longueur 2. Nous proposons une nouvelle classe polynomiale pour ce probleme et exhibons une propriete combinatoire qui pourrait impliquer la polynomialite des differentes classes polynomiale connues. En utilisant le lien existant entre minimisation de fa et recouvrement de bipartis, nous proposons un processus general de minimisation de fa qui repose sur le calcul d'une serie de recouvrements de graphes bipartis issus du fa. Les proprietes generales de ce processus sont etudiees et trois heuristiques differentes sont proposees. Les experimentations effectuees montrent un gain significatif par rapport a un codage par mdfa. L'influence de l'ordre choisi sur les variables sur la taille du mdfa representant un csp est etudiee : nous proposons une borne sur la taille du plus petit mdfa representant un csp ainsi qu'une etude experimentale d'heuristiques d'ordonnancement des variables. Nous proposons des algorithmes specifiques a nos automates pour la realisation des differentes etapes necessaires a la construction d'un petit fa reconnaissant l'ensemble des solutions d'un csp.