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 ${\displaystyle \oplus }$, nommé addition, d'un opérateur binaire ${\displaystyle \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 ${\displaystyle \oplus }$ et définie par ${\displaystyle a\leq b\Leftrightarrow \exists c,~a\oplus c=b}$.

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

• ${\displaystyle (D,\oplus ,0)}$ est un monoïde commutatif ;
• ${\displaystyle (D,\otimes ,1)}$ est un monoïde ;
• ${\displaystyle \otimes }$ est distributif par rapport à ${\displaystyle \oplus }$ ;
• 0 est un élément absorbant pour ${\displaystyle \otimes }$, c'est-à-dire que ${\displaystyle a\otimes 0=0\otimes a=0}$ ;
• la relation ≤ est une relation d'ordre, c'est-à-dire que ${\displaystyle 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 ${\displaystyle a}$ est idempotent pour ${\displaystyle \oplus }$, c'est-à-dire que ${\displaystyle a\oplus a=a}$.

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

Tout demi-anneau idempotent est un dioïde.

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

Voir aussi

• Mathématiques tropicales

Notes et références

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

• Portail de l’algèbre