Dioïde

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

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éfini 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 \land 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 dioï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)

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

Portail de l’algèbre

[1] Jean Kuntzmann, Théorie des réseaux (graphes), Paris, Dunod, 1972, xxiv+288 (zbMATH 0239.05101, SUDOC 002235358).

[2] (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).

[1]

[2]