Demi-anneau

• Les entiers naturels forment un demi-anneau pour l'addition et la multiplication naturelles.
• Les entiers naturels étendus ${\displaystyle \mathbb {N} \cup \{\infty \}}$ avec l'addition et la multiplication étendues et ${\displaystyle 0\cdot \infty =0}$)[2]
• Le demi-anneau de Boole composé de deux éléments 0 et 1. C'est l'algèbre de Boole : ${\displaystyle (\{0,1\},\vee ,\wedge ,0,1)}$ où ${\displaystyle \vee }$ et ${\displaystyle \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[3].
• Un treillis distributif est un demi-anneau commutatif et idempotent pour les lois ${\displaystyle \vee }$ et ${\displaystyle \wedge }$.
• Un treillis dans un anneau est un demi-anneau idempotent pour la multiplication et l'opération ${\displaystyle \nabla }$ définie par ${\displaystyle 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 est nombres réels non négatifs avec les additions et multiplications unsuelles[4]^,[5].
• Le log demi-anneau (en) sur ${\displaystyle \mathbb {R} \cup \{\pm \infty \}}$ avec l’addition donnée par

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

et ${\displaystyle +}$ pour multiplication, élément zéro ${\displaystyle +\infty }$ et élément unité ${\displaystyle 0}$[4].

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

• 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é[6].
• 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[6].
• Plus généralement, l'ensemble des parties d'un monoïde, muni de la réunion et du produit des parties ${\displaystyle U\cdot V=\{u\cdot v\mid u\in U,\ v\in V\}}$ est un demi-anneau[7].
• 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.

• L'ensemble des entiers naturels étendu à ${\displaystyle \infty }$ de façon habituelle (toute somme avec ${\displaystyle \infty }$ donne ${\displaystyle \infty }$ ; tout produit avec ${\displaystyle \infty }$ donne ${\displaystyle \infty }$, sauf pour 0 qui reste absorbant) muni de l'opérateur min et de la somme est un demi-anneau: ${\displaystyle (\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[8] à Dominique Perrin, alors qu'Imre Simon lui-même l'attribue à Christian Choffrut[9]^,[10]. 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[5] : 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.
• ${\displaystyle (\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.

Par transfert de structure :

• Les matrices carrées d'ordre n à entrées dans une 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 (${\displaystyle 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 ${\displaystyle 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}.

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.

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[16]^,[19] :

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

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

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

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

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[6] :

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

avec ${\displaystyle a^{0}=1}$ et ${\displaystyle a^{j+1}=a\cdot a^{j}=a^{j}\cdot a}$ pour ${\displaystyle 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[6].

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