Semi-anneau

 Ne doit pas être confondu avec semi-anneau d'ensembles.

En mathématiques, un semi-anneau, ou un demi-anneau, est une structure algébrique $(E, +, \times, 0, 1)$ telle que

• (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$.

Un demi-anneau est commutatif quand son produit est commutatif.

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

Domaines de prédilection

Les demi-anneaux se retrouvent souvent en :

• recherche opérationnelle : les graphes 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 ;
• théorie des langages et des automates : la concaténation des (ensembles de) chaînes pour en fabriquer d'autres est le produit et l'union des (ensembles de) chaînes est la somme.

Exemples

• Le demi-anneau le plus simple est celui des booléens : $(\{0, 1\}, \vee, \wedge, 0, 1)$ où $\vee$ et $\wedge$ sont OU et ET respectivement.
• Le plus naturel est peut-être celui des entiers positifs avec l'addition et la multiplication: $(\mathbb{N}, +, \times, 0, 1)$.
• 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 le nom de demi-anneau tropical ; il est au cœur des 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.
• $(\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.
• L'ensemble des parties d'un ensemble E muni de l'union et de l'intersection est un semi-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.
• Tout treillis distributif est un semi-anneau.
• Les dioïdes sont des semi-anneaux particuliers.

Bibliographie

• Michel Gondran et Michel Minoux, Graphes, dioïdes et semi-anneaux, Paris, Lavoisier Tec et Doc, 2002, 414 p. (ISBN 978-2-7430-0489-7)