Aller au contenu

Dioïde

Un article de Wikipédia, l'encyclopédie libre.

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

[modifier | modifier le code]

Soit D un ensemble muni d'un opérateur binaire , nommé addition, d'un opérateur binaire , 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 et définie par .

On dit que est un dioïde si :

  • est un monoïde commutatif ;
  • est un monoïde ;
  • est distributif par rapport à  ;
  • 0 est un élément absorbant pour , c'est-à-dire que  ;
  • la relation ≤ est une relation d'ordre, c'est-à-dire que .

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

Terminologie

[modifier | modifier le code]

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

[modifier | modifier le code]

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

Par exemple, est un dioïde idempotent.

Tout demi-anneau idempotent est un dioïde.

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

Notes et références

[modifier | modifier le code]
  1. Jean Kuntzmann, Théorie des réseaux (graphes), Paris, Dunod, , 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 », , xix+489 (ISBN 0-471-93609-X, SUDOC 014487500, lire en ligne).

Bibliographie

[modifier | modifier le code]
  • Michel Gondran et Michel Minoux, Graphes, dioïdes et semi-anneaux : nouveaux modèles et algorithmes, Paris, Tec & Doc, , 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 » (no 41), , 388 p. (ISBN 978-0-387-75450-5, zbMATH 1201.16038, lire en ligne)