Dioïde

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. L'utilisation pour désigner un sous-groupe idempotent a été introduite par Baccelli et al. en 1992.

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

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)

• Michel Minoux, « Algèbre linéaire dans les semi-anneaux et les dioïdes » [PDF], sur HAL, 1998