Congruences represented by partial orders, diamond and lattice properties

S. BAUGET

IBP-Litp 1996/23: Rapport de Recherche Litp / Litp research reports
31 pages - Juin/June 1996 - French document.

PostScript : Ko /Kb

Titre / Title: Congruences represented by partial orders, diamond and lattice properties

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 cet article 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 é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. Nous caractérisons alors notre modèle par des conditions très connues. Les trois propositions suivantes sont équivalentes : (1) la congruence est représentable par ordres partiels et simplifiable à droite ; (2) pour tout mot, l'ordre partiel des préfixes de la classe de ce mot est un treillis distributif ; (3) pour tout mot, l'ordre partiel des préfixes de la classe de ce mot vérifie les deux propriétés de "diamant" : la fermeture dans le passé et la fermeture dans le futur.

Abstract : Mazurkiewicz trace theory is not powerfull enough to describe concurrency paradigms as for instance the "Producer/Consumer". We propose in this paper a generalization of Mazurkiewicz trace monoids which allows us to model such problems. We consider quotients of the freee monoids by congruences which preserve 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 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. And we characterize then our model with well known properties. The tree following assertions are equivalent: (1) the congruence is represented by partial orders and rigth cancellative; (2) for all word, the partial order of prefixes of the class of this word is a distributive lattice; (3) for all word, the partial order of prefixes of the class of this word verifies the two "diamond" properties, the backward and forward closures.


Publications internes Litp 1996 / Litp research reports 1996