Abstract FR:

Une region d'un systeme de transitions est une application de l'ensemble des etats du systeme dans un espace d'evaluation, telle que les variations des valeurs aux extremites de transitions correspondant a la meme action soient uniformes. On etudie en detail le cas ou l'espace d'evaluation est un groupe. Toute region sur un groupe est associee a une application des actions dans le meme groupe, application qu'on appelle contrainte. Les regions et les contraintes d'un systeme de transitions sur un groupe forment deux groupes qui, sous certaines conditions, sont libres et finiment engendres. On montre une caracterisation des contraintes d'ou on derive un algorithme efficace pour le calcul d'une base du groupe des contraintes. L'etude des conditions sous lesquelles un ensemble des regions sur un groupe donne une representation fidele d'un systeme de transitions (c'est-a-dire suffisant a reconstruire le systeme) conduit au probleme de la synthese : decider si un systeme de transitions admet une representation <<<> structurelle <>>> (par opposition a l'aspect <<<> operationnel <>>> du systeme de transition) dans une classe de modeles fixee. On traite ici le probleme pour certaines classes de reseaux de petri, et on montre que dans le cas des reseaux elementaires le probleme est np-complet, tandis que pour les reseaux de places et transitions, finis et bornes, on decrit un algorithme de complexite polynomiale en la taille du systeme de transitions.