Demi-anneau

En mathématiques, un demi-anneau, ou semi-anneau, est une structure algébrique $(E,+,\times ,0,1)$ qui a les propriétés suivantes :

• $(E,+,0)$ constitue un monoïde commutatif ;
• $(E,\times ,1)$ forme un monoïde ;
• $\times$ est distributif par rapport à + ;
• 0 est absorbant pour le produit, autrement dit: pour tout $x\in E:x\times 0=0\times x=0$.

Ces propriétés sont proches de celles d'un anneau, la différence étant qu'il n'y a pas nécessairement d'inverses pour l’addition dans un demi-anneau.

Un demi-anneau est commutatif quand son produit est commutatif ; il est idempotent quand son addition est idempotente. Parfois on distingue les demi-anneaux et les demi-anneaux unifères : dans ce cas, la structure multiplicative n'est qu'un demi-groupe, donc ne possède pas nécessairement un élément neutre. En général, on demande aussi que $0\neq 1$. Un demi-anneau qui ne possède pas nécessairement un élément neutre pour sa multiplication est parfois appelé hémi-anneau (hemiring en anglais).

Contrairement à ce qui se passe pour les anneaux, on ne peut démontrer que 0 est un élément absorbant à partir des autres axiomes.

Domaines d'application

Les demi-anneaux se retrouvent souvent en :

• recherche opérationnelle : les graphes pondérés ont des poids dans un demi-anneau ; le produit est associé à l'accumulation de valeur le long d'un chemin et la somme correspond à la façon de composer plusieurs chemins ; le calcul des plus courts chemins en est un exemple particulier.
• théorie des langages et des automates : la concaténation des (ensembles de) chaînes pour en fabriquer d'autres est le produit. L'union des (ensembles de) chaînes est la somme ;
• théorie des lieux : un lieu est un treillis distributif complet ; la catégorie des lieux généralise celle des espaces topologiques.^{[réf. nécessaire]}

Exemples

Premiers exemples

• Les entiers naturels forment un demi-anneau pour l'addition et la multiplication naturelles.
• Les entiers naturels étendus $\mathbb {N} \cup \{\infty \}$ avec l'addition et la multiplication étendues et $0\cdot \infty =0$).
• Le demi-anneau de Boole composé de deux éléments 0 et 1. C'est l'algèbre de Boole : $(\{0,1\},\vee ,\wedge ,0,1)$ où $\vee$ et $\wedge$ sont OU et ET respectivement.
• En particulier, une algèbre de Boole est un tel demi-anneau. Un anneau de Boole est aussi un demi-anneau — puisque c'est un anneau — mais l'addition n’est pas idempotente. Un demi-anneau de Boole est un demi-anneau qui est isomorphe à un sous-demi-anneau d'une algèbre de Boole.
• Un treillis distributif est un demi-anneau commutatif et idempotent pour les lois $\vee$ et $\wedge$.
• Un treillis dans un anneau est un demi-anneau idempotent pour la multiplication et l'opération $\nabla$ définie par $a\nabla b=a+b+ba-aba-bab$.
• L'ensemble des idéaux d'un anneau forment un demi-anneau pour l'addition et la multiplication d'idéaux.
• Les dioïdes sont des demi-anneaux particuliers.
• Le demi-anneau des probabilités des nombres réels positifs ou nuls, avec les additions et multiplications usuelles.
• Le log demi-anneau (en) sur $\mathbb {R} \cup \{\pm \infty \}$ avec l’addition donnée par

$x\oplus y=-\log(e^{-x}+e^{-y})\ ,$

et $+$ pour multiplication, élément zéro $+\infty$ et élément unité $0$.

• Le demi-anneau de Łukasiewicz est l'intervalle fermé $[0,1]$, avec pour addition $a\oplus b=\max(a,b)$ et pour multiplication $a\otimes b=\max(0,a+b-1)$. Un tel demi-anneau apparaît en logique polyvalente.
• Le demi-anneau de Viterbi est défini sur l'ensemble $[0,1]$, avec l’addition donnée par le maximum et la multiplication usuelle ; il apparait dans l’analyse des grammaires probabilistes.

Exemples généraux

• L'ensemble des parties d'un ensemble E muni de l'union et de l'intersection est un demi-anneau. Les deux lois sont distributives l'une par rapport à l'autre, l'élément neutre de l'union est l'ensemble vide, celui de l'intersection est l'ensemble E. Les deux lois sont commutatives et forment avec E les deux monoïdes requis. C'est une algèbre de Boole et donc un treillis.
• L'ensemble des relations binaires sur un ensemble, avec l'addition donnée par l'union et la multiplication par la composition des relations. Le zéro de ce demi-anneau est la relation vide, et son élément unité la relation identité.
• L'ensemble des langages formels sur un alphabet donné est un demi-anneau avec l'addition donnée par la réunion et le produit par le produit de concaténation des éléments. Le zéro est l'ensemble vide, et l'unité l'ensemble réduit au mot vide.
• Plus généralement, l'ensemble des parties d'un monoïde, muni de la réunion et du produit des parties $U\cdot V=\{u\cdot v\mid u\in U,\ v\in V\}$ est un demi-anneau.
• De même, la famille des parties d'un monoïde M avec multiplicités, c'est-à-dire des sommes formelles d'éléments de M à coefficients entiers naturels forment un demi-anneau. L'addition est la somme formelle avec addition de coefficients, et la multiplication est le produit de Cauchy. La somme nulle est l'élément neutre pour l'addition et le monöme formé de l'élément neutre de M est l'unité pour la multiplication.

Demi-anneau tropical

• L'ensemble des entiers naturels étendu à $\infty$ de façon habituelle (toute somme avec $\infty$ donne $\infty$ ; tout produit avec $\infty$ donne $\infty$, sauf pour 0 qui reste absorbant) muni de l'opérateur min et de la somme est un demi-anneau: $(\mathbb {N} \cup \{\infty \},\min ,+,\infty ,0)$ est connu sous les noms de (min,+)-demi-anneau et demi-anneau tropical, nommé ainsi en l'honneur de son promoteur Imre Simon. La création de l'adjectif tropical est attribuée par Jean-Éric Pin à Dominique Perrin, alors qu'Imre Simon lui-même l'attribue à Christian Choffrut. Le terme tropical fait juste référence aux origines brésiliennes, donc des Tropiques, d'Imre Simon. Cette structure sous-tend les algorithmes de calcul de plus court chemin dans un graphe : les poids sont additionnés le long des chemins et devant plusieurs chemins, on prend le coût minimal. Une variante est le (max,+)-demi-anneau, où le max prend la place de min. Tous deux sont des demi-anneaux tropicaux.
• $(\mathbb {N} \cup \{\infty \},\max ,\min ,0,\infty )$ est le demi-anneau sous-jacent au calcul du flux maximum d'un graphe: dans une séquence d'arcs, celui de poids minimal impose son flux et devant plusieurs séquences, on prend le flux maximal.

Transfert de structure

Par transfert de structure :

• Les matrices carrées d'ordre n à entrées dans un demi-anneau et avec l’addition et la multiplication induites ; ce demi-anneau n'est en général pas commutatif, même si le demi-anneau de ses entrées l’est.
• L'ensemble End(A) des endomorphismes d'un monoïde commutatif A est un demi-anneau avec, pour addition, celle induite par A ($(f+g)(a)=f(a)+g(a)$) et pour multiplication la composition de fonctions. Le morphisme nul et l'identité sont les éléments neutres.
• L'ensemble $S[x]$ des polynômes à coefficients dans un demi-anneau S forment un demi-anneau, commutatif si S l'est, idempotent si S l'est. Si S est l'ensemble des entiers naturels, c'est le demi-anneau libre avec générateur {x}.

Demi-anneau complet et continu

Un monoïde complet est un monoïde commutatif qui possède une opération de sommation infinie $\sum _{I}$ pour tout ensemble d'indices $I$ et tel que les propriétés suivantes sont vérifiées :

$\sum _{i\in \emptyset }{m_{i}}=0;\quad \sum _{i\in \{j\}}{m_{i}}=m_{j};\quad \sum _{i\in \{j,k\}}{m_{i}}=m_{j}+m_{k}\quad {\textrm {pour}}\;j\neq k$

et

$\sum _{j\in J}{\sum _{i\in I_{j}}{m_{i}}}=\sum _{i\in I}(m_{i})\;{\textrm {si}}\bigcup _{j\in J}I_{j}=I\;{\textrm {et}}\;I_{j}\cap I_{j'}=\emptyset \;{\textrm {pour}}\;j\neq j'$

Un monoïde continu est un monoïde ordonné pour lequel tout ensemble ordonné filtrant a une borne supérieure qui de plus est compatible avec l'opération de monoïde :

$a+\sup S=\sup(a+S)\ .$

Les deux concepts sont étroitement liés : un monoïde continu est complet, la somme infinie peut en effet être définie par :

$\sum _{I}a_{i}=\sup \sum _{E}a_{i}$

où le "sup" est pris sur tous les sous-ensembles finis E de I et chaque sommation, dans le membre droit, porte donc sur un ensemble fini.

Un demi-anneau complet est un demi-anneau pour lequel le monoïde additif est un monoïde complet, et qui vérifie les lois de distributivité infinie suivantes :

$\sum _{i\in I}{(a\cdot a_{i})}=a\cdot {\bigl (}\sum _{i\in I}{a_{i}}{\bigl )}$ et $\sum _{i\in I}{(a_{i}\cdot a)}={\bigl (}\sum _{i\in I}{a_{i}}{\bigl )}\cdot a$.

Un exemple de demi-anneaux complet est l'ensemble des parties d'un monoïde pour l'union ; le demi-anneau des matrices à entrées dans un demi-anneau complet est lui-même un demi-anneau complet.

Un demi-anneau continu est un monoïde continu dont la multiplication respecte l'ordre et le bornes supérieures. Le demi-anneau N ∪ {∞} avec l'addition, la multiplication, et l'ordre naturel est une demi-anneau continu.

Tout demi-anneau continu est complet et on peut inclure cette propriété dans la définition.

Demi-anneau étoilé

Un demi-anneau étoilé (en anglais star semiring ou starsemiring est un demi-anneau muni d'un opérateur unaire supplémentaire noté « * » satisfaisant :

$a^{*}=1+aa^{*}=1+a^{*}a.$

Exemples de demi-anneaux étoilés:

• Le demi-anneau de Boole avec 0^∗ = 1^∗ = 1;
• Le demi-anneau des relations binaires sur un ensemble U, où l'étoile d'une relation R est définie par

$R^{*}=\bigcup _{n\geq 0}R^{n}$.

Cette opération est la fermeture réflexive et transitive de la relation R.

• Le demi-anneau des langages formels est un demi-anneau étoilé complet, l'opération étoile étant l'étoile de Kleene.
• L'ensemble des nombres réels positifs augmentés de ∞, avec l'addition et la multiplication usuelles est un demi-anneau complet étoilé avec l'opération étoile donnée par a^∗ = 1/(1 − a) pour 0 ≤ a < 1 (la série géométrique usuelle) et a^∗ = ∞ pour a ≥ 1.
• Le demi-anneau N ∪ {∞}, avec addition et multiplication étendues, et 0^∗ = 1, a^∗ = ∞ pour a ≥ 1.

Algèbre de Kleene

Une algèbre de Kleene est un demi-anneau étoilé avec une addition idempotente; elles interviennent en théorie des langages et dans les expressions régulières.

Demi-anneau de Conway

Un demi-anneau de Conway est un demi-anneau étoilé qui vérifie les équations suivantes entre l'opération étoile et l’addition et la multiplication :

$(a+b)^{*}=(a^{*}b)^{*}a^{*},\,$

$(ab)^{*}=1+a(ba)^{*}b.\,$

Les trois premiers exemples ci-dessus sont aussi des demi-anneaux de Conway.

Demi-anneau itératif

Un demi-anneau itératif (en anglais iteration semiring) est un demi-anneau de Conway qui vérifie les axiomes de Conway des groupes associés par John Conway aux groupes dans les demi-anneaux étoilés

Demi-anneau étoilé complet

Un demi-anneau étoilé complet est un demi-anneau où l'étoile a les propriétés habituelles de l'étoile de Kleene ; on la définit à l'aide de l'opérateur de sommation infinie par :

$a^{*}=\sum _{j\geq 0}{a^{j}}$

avec $a^{0}=1$ et $a^{j+1}=a\cdot a^{j}=a^{j}\cdot a$ pour $j\geq 0$.

Les demi-anneaux des relations binaires, des langages formels et des nombres réels non négatifs étendus sont étoilés complets.

Un demi-anneau étoilé complet est aussi un demi-anneau de Conway mais la réciproque n'est pas vraie. Un exemple est fourni par les nombres rationnels non négatifs étendus $\{x\in \mathbb {Q} \mid x\geq 0\}\cup \{\infty \}$ avec l’addition et la multilication usuelles.

Bibliographie

• Claude Pair, « Sur des algorithmes pour des problèmes de cheminement dans les graphes finis », dans P. Rosentiehl, Théorie des graphes (journées internationales d'études) -- Theory of Graphs (internainal symposium), Dunod (Paris) et Gordon and Breach (New York), 1966
• Jean Claude Derniame et Claude Pair, Problèmes de cheminement dans les graphes, Dunod (Paris), 1971, 182 p.
• Kazimierz Głazek, A guide to the literature on semirings and their applications in mathematics and information sciences. With complete bibliography, Dordrecht, Kluwer Academic, 2002 (ISBN 1-4020-0717-5, zbMATH 1072.16040)
• Jonathan S. Golan, Semirings and their Applications, Dordrecht, Kluwer Academic Publishers (Springer Science & Business Media), 1999, xii+ 381 (ISBN 978-0-7923-5786-5, MR 1746739, lire en ligne) — Édition revue et augmentée de (en) The theory of semirings, with applications to mathematics and theoretical computer science, Harlow, Longman Scientific & Technical et John Wiley & Sons, coll. « Pitman Monographs and Surveys in Pure and Applied Mathematics », 1992, xiv+318 (ISBN 0-582-07855-5, MR 1163371)
• (en) M. Lothaire, Applied combinatorics on words, Cambridge (GB), Cambridge University Press, coll. « Encyclopedia of Mathematics and its Applications » (n^o 105), 2005, 610 p. (ISBN 978-0-521-84802-2, zbMATH 1133.68067, lire en ligne)
• 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, xix+383 (ISBN 978-0-387-75450-5, zbMATH 1201.16038, SUDOC 12874958X, lire en ligne)
• (en) Jacques Sakarovitch, Elements of automata theory (Translated from the French by Reuben Thomas), Cambridge, Cambridge University Press, 2009, 758 p. (ISBN 978-0-521-84425-3, zbMATH 1188.68177)
• Jean Berstel et Christophe Reutenauer, Noncommutative rational series with applications, Cambridge, Cambridge University Press, coll. « Encyclopedia of Mathematics and Its Applications » (n^o 137), 2011, 248 p. (ISBN 978-0-521-19022-0, zbMATH 1250.68007, lire en ligne)
• Manfred Droste et Werner Kuich, « Semirings and Formal Power Series », dans Manfred Droste, Werner Kuich, Heiko Vogler (éditeurs),, Handbook of Weighted Automata, Springer-Verlag, 2009 (DOI 10.1007/978-3-642-01492-5_1), p. 3-29
• Zoltán Ésik, « Iteration semirings », dans Masami Ito (éditeur), Developments in language theory (12th international conference, DLT 2008, Kyoto, Japan, September 16–19, 2008)., Berlin, Springer-Verlag, coll. « Lecture Notes in Computer Science » (n^o 5257), 2008 (ISBN 978-3-540-85779-2, DOI 10.1007/978-3-540-85780-8_1, zbMATH 1161.68598), p. 1–20
• Zoltán Ésik et Werner Kuich, « Equational axioms for a theory of automata », dans Carlos Martín-Vide, Formal languages and applications, Berlin, Springer-Verlag, coll. « Studies in Fuzziness and Soft Computing » (n^o 148), 2004 (ISBN 3-540-20907-7, zbMATH 1088.68117), p. 183–196
• Werner Kuich, « Algebraic systems and pushdown automata », dans Werner Kuich, Algebraic foundations in computer science. Essays dedicated to Symeon Bozapalidis on the occasion of his retirement, Berlin, Springer-Verlag, coll. « Lecture Notes in Computer Science » (n^o 7020), 2011 (ISBN 978-3-642-24896-2, zbMATH 1251.68135), p. 228–256.