Modélisation du parallélisme par congruences et ordres partiels

S. BAUGET

IBP-Litp 1996/Th/02: THÈSE de DOCTORAT de l'UNIVERSITÉ PARIS 6 Litp / Litp research reports
125 pages - Mars/March 1996 - French document.

PostScript : Ko /Kb

Titre / Title: Modélisation du parallélisme par congruences et ordres partiels

Résumé : La théorie des traces de Mazurkiewicz n'est pas suffisamment puissante pour décrire certains paradigmes de la concurrence comme celui du "Producteur/Consommateur". On propose dans cette thèse une généralisation des monoïdes de traces qui permet de modéliser de tels problèmes. On considère des quotients du monoïde libre par des congruences qui préservent l'image commutative des mots. Une classe d'équivalence dans le monoïde consiste en toutes les observations séquentielles d'un comportement distribué. Afin de caractériser les congruences qui représentent réellement les systèmes distribués, on compare notre approche à la modélisation classique de la concurrence au moyen d'ordres partiels. On montre que les seules congruences dont les classes sont représentables par un ordre partiel et pour lesquelles la concaténation s'exprime modulairement sur ces ordres partiels sont les congruences detraces de Mazurkiewcz. On établit ensuite des conditions nécessaires et des conditions suffisantes sur ces congruences pour que leurs classes soient représentables par ordres partiels. En particulier, une condition suffisante importante couvre à la fois le cas des traces et le paradigme du "Producteur/Consommateur". Dans une deuxième partie, nous optons pour une autrre approche de ces congruences représentables par ordres partiels. Il s'agit de représenter la classe d'un mot par l'ordre partiel des préfixes de cette classe. Et nous caractérisons notre modèle par des conditions très connus : les fermetures des diamants dans le passé et le futur. Nous terminons dans la troisième partie, par une étude de la reconnaissabilité dans les monïdes quotients d'un monoïde libre par une congruence qui préserve l'image commutative.

Abstract : Mazurkiewicz trace theory is not powerfull enough to describe concurrency paradigms as for instance the "Producer/Consumer". We propose in this thesis a generalization of Mazurkiewicz trace monoids which allows us to model such problems. We consider quotients of the freee monoids by congruences which preseve the commutative image of words. An equivalence class in the quotient monoid consists of all the sequential observations of a distributed computation. In order to characterize congruences which do model concurrency, we study the relation ship of this approach and the classical representation of distributed computations with partial orders. We show that the only congruences for which the classes can be represented by partial ordres and the concatenation transfers modulary to partial orders are congruences generated by commutations, that is trace congruences. We prove necessary conditions and sufficient conditions on congruences so that their classes can be represented by partial orders. In particular, an important sufficient condition covers both trace congruences and the "Producer/Consumer" congruence. In the second part, we opt for another approach of these congruences which are represented by partial orders. We represent the class of a word with the partial order of its prefixes. An we characterize then our model with well known conditions: the backward and forward diamond closures. And we end in the last part with a study of the recognizability in the monoids quotients of a free monoid by a congruence which preserves the commutative image.

Publications internes Litp 1996 / Litp research reports 1996