Ouvrir le menu principal

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.

Sommaire

DéfinitionModifier

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.

TerminologieModifier

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 idempotentModifier

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érencesModifier

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

BibliographieModifier

  • Michel 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, SUDOC 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, zbMATH 1201.16038)