Dioïde

Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

En mathématiques et en informatique, un dioïde est un demi-anneau dans lequel le préordre défini par l'addition est une relation d'ordre.

Définition

Soit D un ensemble muni d'un opérateur binaire $\oplus$ , nommé addition, d'un opérateur binaire $\otimes$ , nommé produit, et dans lequel sont spécifiés deux éléments distincts, notés 0 et 1.

On note ≤ le préordre associé à l'opérateur $\oplus$ et définie par $a\leq b\Leftrightarrow \exists c,~a\oplus c=b$ .

On dit que $(D,\oplus ,\otimes ,0,1)$ est un dioïde si :

$(D,\oplus ,0)$ est un monoïde commutatif ;
$(D,\otimes ,1)$ est un monoïde ;
$\otimes$ est distributif par rapport à $\oplus$ ;
0 est un élément absorbant pour $\otimes$ , c'est-à-dire que $a\otimes 0=0\otimes a=0$ ;
la relation ≤ est une relation d'ordre, c'est-à-dire que $a\leq b\wedge b\leq a\Rightarrow a=b$ .

Si l'on omet le dernier point, la structure définie est un demi-anneau.

Terminologie

Le nom de droïde provient du fait qu'il combine deux monoïdes, comme tout demi-anneau (en particulier tout anneau). Ce nom a été employé par Jean Kuntzmann en 1972 pour la structure appelée maintenant demi-anneau^[1]. L'utilisation pour désigner un sous-groupe idempotent a été introduite par Baccelli et al. en 1992^[2].

Les dioïdes et les anneaux sont tous deux des demi-anneaux, mais ils sont exclusifs les uns des autres.

Dioïde idempotent

Le dioïde idempotent est la classe de dioïdes la plus utilisée. Il se caractérise le fait que tout élément $a$ est idempotent pour $\oplus$ , c'est-à-dire que $a\oplus a=a$ .

Par exemple, $([-\infty ,+\infty [,\max ,+,-\infty ,0)$ est un dioïde idempotent.

Tout demi-anneau idempotent est un dioïde.

Démonstration

Il s'agit de prouver que la relation de préordre est un ordre. Si $a\leq b$ alors il existe c tel que $a\oplus c=b$ , d'où

b=a\oplus c=a\oplus a\oplus c=a\oplus b

.

De même, si $b\leq a$ alors $a=b\oplus a$ . Par conséquent, si $a\leq b$ et $b\leq a$ , alors en utilisant la commutativité de $\oplus$ on obtient

b=a\oplus b=b\oplus a=a

.

Les demi-anneaux idempotents sont donc exactement les dioïdes idempotents.

Voir aussi

Mathématiques tropicales

Notes et références

↑ Jean Kuntzmann, Théorie des réseaux (graphes), Paris, Dunod, 1972, xxiv+288 (zbMATH 0239.05101, SUDOC 002235358).
↑ (en) Francois Baccelli, Guy Cohen, Geert Jan Olsder et Jean-Pierre Quadrat, Synchronization and Linearity : An Algebra for Discrete Event Systems, Chichester, Wiley, coll. « Wiley Series on Probability and Mathematical Statistics », 1992, xix+489 (ISBN 0-471-93609-X, SUDOC 014487500, lire en ligne).

Bibliographie

Michel Gondran et Michel Minoux, Graphes, dioïdes et semi-anneaux : nouveaux modèles et algorithmes, Paris, Tec & Doc, 2001, xvi+415 (ISBN 2-7430-0489-4, SUDOC 060235101) — Édition en anglais : (en) Michel Gondran et Michel Minoux, Graphs, Dioids and Semirings : New Models and Algorithms, Dordrecht, Springer Science & Business Media, coll. « Operations Research/Computer Science Interfaces Series » (n^o 41), 2008, 388 p. (ISBN 978-0-387-75450-5, zbMATH 1201.16038, lire en ligne)