0 est absorbant pour le produit, autrement dit: pour tout .
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 . 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)[1].
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 ;
Les entiers naturels forment un demi-anneau pour l'addition et la multiplication naturelles.
Les entiers naturels étendus avec l'addition et la multiplication étendues et )[2]
Le demi-anneau de Boole composé de deux éléments 0 et 1. C'est l'algèbre de Boole : où et 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 et .
Un treillis dans un anneau est un demi-anneau idempotent pour la multiplication et l'opération définie par .
L'ensemble des idéaux d'un anneau forment un demi-anneau pour l'addition et la multiplication d'idéaux.
et pour multiplication, élément zéro et élément unité [4].
Le demi-anneau de Łukasiewicz est l'intervalle fermé , avec pour addition et pour multiplication . Un tel demi-anneau apparaît en logique polyvalente[6].
Le demi-anneau de Viterbi est défini sur l'ensemble , avec l’addition donnée par le maximum et la multiplication usuelle ; il apparait dans l’analyse des grammaires probabilistes[6].
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é[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 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 à de façon habituelle (toute somme avec donne ; tout produit avec donne , sauf pour 0 qui reste absorbant) muni de l'opérateur min et de la somme est un demi-anneau: 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.
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.
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 () et pour multiplication la composition de fonctions. Le morphisme nul et l'identité sont les éléments neutres.
L'ensemble 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 pour tout ensemble d'indices et tel que les propriétés suivantes sont vérifiées[6],[11],[12],[13] :
et
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 :
Les deux concepts sont étroitement liés : un monoïde continu est complet, la somme infinie peut en effet être définie par :
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[13].
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[13],[6],[12] :
et .
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[14].
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[15].
Tout demi-anneau continu est complet[13] et on peut inclure cette propriété dans la définition[14].
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[16],[6],[17],[18] :
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
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[6].
Le demi-anneau N ∪ {∞}, avec addition et multiplication étendues, et 0∗ = 1, a∗ = ∞ pour a ≥ 1.
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] :
Les trois premiers exemples ci-dessus sont aussi des demi-anneaux de Conway[6].
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[16] associés par John Conway aux groupes dans les demi-anneaux étoilés[20]
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[6] :
avec et pour .
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 avec l’addition et la multilication usuelles[6].
↑Alexander E. Guterman, « Rank and determinant functions for matrices over semirings », dans Nicholas Young et Yemon Choi (éditeurs), Surveys in Contemporary Mathematics, Cambridge University Press, coll. « London Mathematical Society Lecture Note Series » (no 347), (ISBN0-521-70564-9, zbMATH1181.16042), p. 1–33.
↑ a et bClaude 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),
↑Jean-Éric Pin, « Tropical Semirings », dans J. Gunawardena, Idempotency (Bristol, 1994), Cambridge, Cambridge University Press, coll. « Publ. Newton Inst. 11 », 1998,, p. 50-69.
↑Imre Simon, « Recognizable sets with multiplicities in the tropical semiring », dans Mathematical Foundations of Computer Science (Carlsbad, 1988), Springer, coll. « Lecture Notes in Computer Science » (no 324), (lire en ligne), p. 107–120.
↑Udo Hebisch, « Eine algebraische Theorie unendlicher Summen mit Anwendungen auf Halbgruppen und Halbringe », Bayreuther Mathematische Schriften, vol. 40, , p. 21–152 (zbMATH0747.08005)
↑ a et bWerner Kuich, « ω-continuous semirings, algebraic systems and pushdown automata », dans Michael S. Paterson (éditeur), Automata, Languages and Programming (17th International Colloquium, Warwick University, England, July 16-20, 1990), Springer-Verlag, coll. « Lecture Notes in Computer Science » (no 443), (ISBN3-540-52826-1), p. 103–110
↑Zoltán Ésik et Hans Leiß, « Greibach normal form in algebraically complete semirings », dans Julian Bradfield, Computer Science Logic (16th international workshop, CSL 2002, 11th annual conference of the EACSL, Edinburgh, Scotland, September 22-25, 2002), Berlin, Springer-Verlag, coll. « Lecture Notes in Computer Science » (no 2471), (zbMATH1020.68056), p. 135–150.
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),
Jean Claude Derniame et Claude Pair, Problèmes de cheminement dans les graphes, Dunod (Paris), , 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, (ISBN1-4020-0717-5, zbMATH1072.16040)
Jonathan S. Golan, Semirings and their Applications, Dordrecht, Kluwer Academic Publishers (Springer Science & Business Media), , xii+ 381 (ISBN978-0-7923-5786-5, MR1746739, 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 », , xiv+318 (ISBN0-582-07855-5, MR1163371)
Manfred Droste et Werner Kuich, « Semirings and Formal Power Series », dans Manfred Droste, Werner Kuich, Heiko Vogler (éditeurs),, Handbook of Weighted Automata, Springer-Verlag, (DOI10.1007/978-3-642-01492-5_1), p. 3-29
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 » (no 148), (ISBN3-540-20907-7, zbMATH1088.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 » (no 7020), (ISBN978-3-642-24896-2, zbMATH1251.68135), p. 228–256.