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 , 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

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 parBaccelli 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 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

  1. Jean Kuntzmann, Théorie des réseaux (graphes), Paris, Dunod, , xxiv+288 p. (0239.05101, 002235358).
  2. 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 p. (ISBN 047193609X, lire en ligne).

Bibliographie

  • Gondran et Michel Minoux, Graphes, dioïdes et semi-anneaux : nouveaux modèles et algorithmes, Paris, Tec & Doc, , xvi+415 p. (ISBN 2-7430-0489-4, 060235101) — Édition en anglais : 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), (ISBN 978-0-387-75450-5, 1201.16038)