On congruences and partial orders

S. Bauget, P. Gastin

IBP-Litp 1995/14: Rapport de Recherche Litp / Litp research reports
13 pages - Mars/March 1995 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: On congruences and partial orders

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 ce papier 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 quotient consiste en toutes les observations séquentielles d'un comportement distribué. Afin de caractériser les congruences qui modélisent 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 ordres partiels et pour lesquelles la concaténation s'exprime modulairement sur les ordres partiels sont celles engendrées par des commutations, c'est à dire les congruences des traces de Mazurkiewicz. On établit des conditions nécessaires et des conditions suffisantes sur les congruences pour que leurs classes d'équivalence soient représentables par ordres partiels. En particulier, une condition suffisante intéressante couvre à la fois les congruences des traces et l'exemple du "Producteur / Consommateur".

Abstract : Mazurkiewicz trace theory is not powerful enough to describe concurrency paradigms as, for instance, the "Producer / Consumer". We propose in this paper a generalization of Mazurkiewicz trace monoids which allows to model such problems. We consider quotients of the free monoids by congruences which preserve the commutative images 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 relationship 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 orders and for which the concatenation transfers modularly 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.

Publications internes Litp 1995 / Litp research reports 1995