Semianneau

Un article de Wikipédia, l'encyclopédie libre.

Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).

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: un anneau se construit de façon similaire à partir d'un groupe additif et d'un monoïde multiplicatif mais il n'a pas besoin du dernier axiome car l'absorption du zéro se déduit de l'inversibilité de la somme.

[modifier] 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.

[modifier] 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.