Halv ring

I matematik , en halv-ring , eller semi-ring , er en algebraisk struktur , der har følgende egenskaber: $(E, +, \ gange, 0,1)$

$(E, +, 0)$ udgør en kommutativ monoid ;
$(E, \ gange, 1)$ danner en monoid ;
$\ gange$ er distribuerende med hensyn til +;
0 absorberer for produktet, med andre ord: for alt . $x \ i E: x \ gange 0 = 0 \ gange x = 0$

Disse egenskaber svarer til egenskaberne ved en ring , idet forskellen er, at der ikke nødvendigvis er inverser for tilføjelsen i en halvring.

En halvring er kommutativ, når dens produkt er kommutativ; det er idempotent, når dets tilføjelse er idempotent . Nogle gange skelner man mellem halvringene og de samlede halve ringe : i dette tilfælde er den multiplikative struktur kun en halvgruppe og har derfor ikke nødvendigvis et neutralt element. Generelt beder vi også om det . En halv ring, der ikke nødvendigvis har et neutralt element til multiplikation, kaldes undertiden hemi-ring ( hemiring engelsk). $0 \ neq 1$

I modsætning til hvad der sker for ringe , kan vi ikke bevise, at 0 er et absorberende element fra de andre aksiomer.

Anvendelsesområder

Halvringe findes ofte i:

operationer forskning : vægtede grafer har vægte i en halv ring; produktet er forbundet med akkumulering af værdi langs en sti, og summen svarer til måden at komponere flere stier på beregningen af de korteste stier er et særligt eksempel.
Teori om sprog og automatik : sammenkædning af (sæt) strenge for at skabe andre er produktet. Sammenslutningen af (sæt) strenge er summen;
teori om steder: et sted er et komplet distribuerende gitter ; den kategori af steder generaliserer at af topologiske rum .

Eksempler

Første eksempler

De naturlige tal danner en halvring for tilføjelsen og multiplikationen naturlig.
Udvidede naturlige tal med udvidet tilføjelse og multiplikation og ) ${\ displaystyle \ mathbb {N} \ cup \ {\ infty \}}$ ${\ displaystyle 1 = 0 \ cdot \ infty = 0}$
Den boolske halvring sammensat af to elementer 0 og 1. Dette er den boolske algebra : hvor og er henholdsvis OR og AND . $(\ {0.1 \}, \ vee, \ wedge, 0.1)$ $\ vee$ $\ kile$
Især er en boolsk algebra sådan en halvring. En Boole-ring er også en halv ring - da det er en ring - men tilføjelsen er ikke ubetydelig. En boolsk halvring er en halvring, der er isomorf til en underhalvring af en boolsk algebra.
Et distribuerende gitter er en kommutativ halvring og idempotent for lovene og . $\ vee$ $\ kile$
Et gitter i en ring er et halvt ring idempotent til multiplikation og operation defineret af . $\ nabla$ ${\ displaystyle a \ nabla b = a + b + ba-aba-bab}$
Sættet af idealer i en ring danner en halvring til tilføjelse og multiplikation af idealer.
De dioids er halvt ringe individer.
Den halve ring af sandsynligheder er ikke-negative reelle tal med mislykket addition og multiplikation.
Den log halvring (i) på med tilsætning givet ved ${\ displaystyle \ mathbb {R} \ cup \ {\ pm \ infty \}}$

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

og til multiplikation, element nul og element enhed .

+

+ \ infty

{\ displaystyle 0}

Łukasiewicz- halvringen er det lukkede interval med tilføjelse og multiplikation . En sådan halvring fremtræder i polyvalent logik . $[0,1]$ ${\ displaystyle a + b = \ max (a, b)}$ ${\ displaystyle ab = \ max (0, a + b-1)}$
Viterbi- halvringen er defineret på sættet , med tilføjelsen givet ved den maksimale og den sædvanlige multiplikation; det fremgår af analysen af sandsynlige grammatikker . $[0,1]$

Generelle eksempler

Sættet med dele af et sæt E forsynet med samlingen og krydset er en halvring. De to love er fordelende i forhold til hinanden, det neutrale element i foreningen er det tomme sæt, det i skæringspunktet er det sæt E. De to love er kommutative og danner sammen med E de to monoider, der kræves. Det er en boolsk algebra og derfor et gitter .
Sættet med binære relationer over et sæt med den tilføjelse, der gives af foreningen, og multiplikationen med sammensætningen af forholdene. Nulet i denne halvring er den tomme relation, og dens enhedselement identitetsrelationen.
Sættet med formelle sprog på et givet alfabet er en halvring med den tilføjelse, der gives af foreningen og produktet ved produktet af sammenkædningen af elementerne. Nul er det tomme sæt, og enheden sættet reduceres til det tomme ord.
Mere generelt er sæt af dele af en monoid forsynet med foreningen og produktet af delene en halvring. ${\ displaystyle U \ cdot V = \ {u \ cdot v \ mid u \ i U, \ v \ i V \}}$
Ligeledes danner familien af dele af en monoid M med multiplikationer, det vil sige formelle summer af elementer af M med naturlige heltalskoefficienter en halvring. Tilsætning er den formelle sum med tilføjelse af koefficienter, og multiplikationen er Cauchy-produktet. Nulsummen er det neutrale element til addition, og monomet dannet af det neutrale element i M er enheden til multiplikation.

Tropisk halvring

Sættet af naturlige tal udvidet til på den sædvanlige måde (enhver sum med giver ; ethvert produkt med giver , bortset fra 0, der forbliver absorberende) leveret med operatøren min og summen er en halvring: er kendt under navnene de ( min, +) - tropisk halvring og halvring , så navngivet til ære for sin promotor Imre Simon . Oprettelsen af adjektivet tropisk tilskrives Jean-Éric Pin til Dominique Perrin, mens Imre Simon selv tilskriver det Christian Choffrut. Udtrykket tropisk refererer bare til den brasilianske oprindelse, derfor troperne, af Imre Simon. Denne struktur ligger til grund for algoritmerne til beregning af den korteste sti i en graf: vægtene tilføjes langs stierne og foran flere stier tager vi de minimale omkostninger. En variant er (max, +) - halvring, hvor max træder i stedet for min . Begge er tropiske halvringe. $\ infty$ $\ infty$ $\ infty$ $\ infty$ $\ infty$ $({\ mathbb {N}} \ cup \ {\ infty \}, \ min, +, \ infty, 0)$
$({\ mathbb {N}} \ cup \ {\ infty \}, \ max, \ min, 0, \ infty)$ er den halve ring, der ligger til grund for beregningen af den maksimale flux af en graf: i en sekvens af buer påtager den af minimumsvægt sin flux og foran flere sekvenser tager vi den maksimale flux.

Overførsel af struktur

Ved overførsel af struktur :

De firkantede matricer af rækkefølge n med input i en halvring og med den inducerede addition og multiplikation; denne halvring er generelt ikke kommutativ, selvom halvringen af dens indgange er.
Den indstillede ende ( A ) af endomorfismen af en kommutativ monoid A er en halvring med, derudover, induceret af A ( ) og til multiplikation sammensætningen af funktioner . Nullmorfismen og identiteten er de neutrale elementer. ${\ displaystyle f + g (a) = f (a) + g (a)}$
Sættet af polynomer med koefficienter i en halvring S danner en halvring, kommutativ, hvis S er, idempotent, hvis S er. Hvis S er sættet med naturlige heltal, er det den gratis halvring med generator { x }. ${\ displaystyle S [x]}$

Fuld og kontinuerlig halvring

En komplet monoid er en kommutativ monoid, der har en uendelig summeringsoperation for ethvert sæt indeks og sådan, at følgende egenskaber holder: ${\ displaystyle \ sum _ {I}}$ $jeg$

{\ displaystyle \ 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 {for}} \; j \ neq k}

{\ displaystyle \ 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 {and}} \; I_ {j} \ cap I_ {j '} = \ emptyset \; { \ textrm {for}} \; j \ neq j '}

En kontinuerlig monoid er en ordnet monoid, for hvilken ethvert filtreret bestilt sæt har en øvre grænse, som desuden er kompatibel med monoid-operationen:

${\ displaystyle a + \ sup S = \ sup (a + S) \.}$

De to begreber er nært beslægtede: en kontinuerlig monoid er komplet, den uendelige sum kan faktisk defineres ved:

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

hvor "sup" tages på alle de endelige undergrupper E af I, og hver opsummering i det rigtige medlem vedrører derfor et endeligt sæt.

En komplet halvring er en halvring, for hvilken additivet monoid er en komplet monoid, og som opfylder følgende uendelige fordelingslove:

{\ displaystyle \ sum _ {i \ i I} {(a \ cdot a_ {i})} = a \ cdot {\ bigl (} \ sum _ {i \ i I} {a_ {i}} {\ bigl )}}

og .

{\ displaystyle \ sum _ {i \ i I} {(a_ {i} \ cdot a)} = {\ bigl (} \ sum _ {i \ i I} {a_ {i}} {\ bigl)} \ cdot a}

Et eksempel på en komplet halvring er sættet af dele af en monoid til foreningen; halvringen af indgangen dør i en komplet halvring er i sig selv en komplet halvring.

En kontinuerlig halvring er en kontinuerlig monoid, hvis multiplikation respekterer rækkefølgen og de øvre grænser. Den halve ring N ∪ {∞} med addition, multiplikation og den naturlige orden er en kontinuerlig halvring.

Enhver kontinuerlig halvring er komplet, og denne egenskab kan inkluderes i definitionen.

Stjerneklar halvring

En stjerne- halvring (på engelsk star semiring eller starsemiring er en halvring forsynet med en ekstra unary operator bemærket "*" tilfredsstillende:

{\ displaystyle a ^ {*} = 1 + aa ^ {*} = 1 + a ^ {*} a.}

Eksempler på stjernehalvringe:

Halvringen af Boole med 0 ∗ = 1 ∗ = 1 ;
Halvringen af binære relationer på et sæt U , hvor stjernen i en relation R er defineret af

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

. Dette er den refleksive og transitive lukning af relationen R .

Halvringen af formelle sprog er en komplet halvstjerne ring, hvor stjerneoperationen er Kleenes stjerne .
Sættet af positive reelle tal steg med ∞, med den sædvanlige tilføjelse og multiplikation er en komplet stjernehalvring med stjerneoperationen givet af a ∗ = 1 / (1 - a ) for 0 ≤ a <1 (den sædvanlige geometriske række ) og a ∗ = ∞ for a ≥ 1 .
Den halve ring N ∪ {∞}, med udvidet addition og multiplikation, og 0 * = 1 , en * = ∞ for en ≥ 1 .

Kleene algebra

En Kleene-algebra er en stjerneklar halvring med idempotent tilsætning; de er involveret i sprogteori og i regulære udtryk .

Half Conway Ring

En Conway- halvring er en stjerneformet halvring, der opfylder følgende ligninger mellem stjernedrift og addition og multiplikation:

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

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

De første tre eksempler ovenfor er også halve Conway-ringe.

Iterativ halvring

En halvring iterativ (engelsk iteration semiring ) Conway er en halvring, hvoraf kontrolleres Conway-aksiomgrupper forbundet med John Conway- grupper i de halvringe

Halvring med fuld stjerne

En halvstjerners halvring er en halvring, hvor stjernen har de sædvanlige egenskaber for Kleenes stjerne ; vi definerer det ved hjælp af den uendelige summeringsoperator ved:

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

med og for . ${\ displaystyle a ^ {0} = 1}$ ${\ displaystyle a ^ {j + 1} = a \ cdot a ^ {j} = a ^ {j} \ cdot a}$ ${\ displaystyle j \ geq 0}$

Halvringene af binære relationer, formelle sprog og udvidede ikke-negative reelle tal er fuldstjernede.

En komplet halvstjerne ring er også en halv Conway ring, men det omvendte er ikke sandt. Et eksempel tilvejebringes af de udvidede ikke-negative rationelle tal med den sædvanlige tilføjelse og multilicering. ${\ displaystyle \ {x \ in \ mathbb {Q} \ mid x \ geq 0 \} \ cup \ {\ infty \}}$

Noter og referencer

Golan 1999 , s. 1.
Sakarovich 2009 , s. 28.
Alexander E. Guterman, ”Rank and determinant functions for matrics over semirings” , i Nicholas Young og Yemon Choi (eds), Surveys in Contemporary Mathematics , Cambridge University Press , koll. "London Mathematical Society Note Play Series" ( nr . 347)2008( ISBN 0-521-70564-9 , zbMATH 1181.16042 ) , s. 1–33.
Lothaire 2005 , s. 211.
Claude Pair, "Om algoritmer til flowproblemer i endelige grafer" , i P. Rosentiehl, Théorie des graphes (internationale studiedage) - Theory of Graphs (internainal symposium) , Dunod (Paris) og Gordon and Breach (New York),1966
Droste og Kuich 2009 , s. 7-10.
Berstel og Reutenauer 2011 , s. 4.
Jean-Éric Pin, “Tropical Semirings” , i J. Gunawardena, Idempotency (Bristol, 1994) , Cambridge, Cambridge University Press, koll. "Publ. Newton Inst. 11 ”, 1998 ,, s. 50-69 .
Imre Simon, "Genkendelige sæt med mangfoldigheder i den tropiske semiring" , i Mathematical Foundations of Computer Science (Carlsbad, 1988) , Springer, coll. "Forelæsningsnotater inden for datalogi" ( nr . 324), 1988( læs online ) , s. 107–120.
Mathoverflow 2011, Hvad er tropisk om tropisk algebra? på Mathoverflow
Udo Hebisch , " Eine algebraische Theorie unendlicher Summen mit Anwendungen auf Halbgruppen und Halbringe ", Bayreuther Mathematische Schriften , bind. 40,1992, s. 21–152 ( zbMATH 0747.08005 )
Werner Kuich , “ω kontinuerlige semiringer, algebraiske systemer og pushdown-automata” , i Michael S. Paterson (redaktør), Automata, sprog og programmering (17. internationale kollokvium, Warwick University, England, 16.-20. Juli) , 1990) , Springer-Verlag , koll. "Forelæsningsnotater inden for datalogi" ( nr . 443), 1990( ISBN 3-540-52826-1 ) , s. 103–110
Kuich 2011 .
Sakarovich 2009 , s. 471.
Zoltán Ésik og Hans Leiß , “Greibach normal form i algebraisk komplette semirings” , i Julian Bradfield, Computer Science Logic (16. internationale workshop, CSL 2002, 11. årlige konference i EACSL, Edinburgh, Skotland, 22.-25. September 2002) , Berlin, Springer-Verlag , koll. "Forelæsningsnotater inden for datalogi" ( nr . 2471), 2002( zbMATH 1020.68056 ) , s. 135-150.
Esik 2008 .
Daniel J. Lehmann, " Algebraiske strukturer til transitiv lukning ", Teoretisk datalogi , bind. 4, n o 1,1977, s. 59-76.
Berstel og Reutenauer 2011 , s. 27.
Esik og Kuich 2004 .
John H. Conway , Almindelige algebra- og endelige maskiner , London, Chapman og Hall,1971( ISBN 0-412-10620-5 , zbMATH 0231.94041 )
Droste og Kuich 2009 , sætning 3.4 s. 15 .

Bibliografi

Claude Pair, "Om algoritmer til flowproblemer i endelige grafer" , i P. Rosentiehl, Théorie des graphes (internationale studiedage) - Theory of Graphs (internainal symposium) , Dunod (Paris) og Gordon and Breach (New York),1966
Jean Claude Derniame og Claude Pair, Problemer med progression i grafer , Dunod (Paris),1971, 182 s.
Kazimierz Głazek , En guide til litteraturen om seminarer og deres anvendelser inden for matematik og informationsvidenskab. Med komplet bibliografi , Dordrecht, Kluwer Academic,2002( ISBN 1-4020-0717-5 , zbMATH 1072.16040 )
Jonathan S. Golan, Semirings og deres applikationer , Dordrecht, Kluwer Academic Publishers (Springer Science & Business Media),1999, xii + 381 s. ( ISBN 978-0-7923-5786-5 , Matematiske anmeldelser 1746739 , læs online )- Revideret og udvidet udgave af (en) Semiringsteorien med anvendelser til matematik og teoretisk datalogi , Harlow, Longman Scientific & Technical og John Wiley & Sons, coll. "Pitman-monografier og undersøgelser inden for ren og anvendt matematik",1992, xiv + 318 s. ( ISBN 0-582-07855-5 , matematiske anmeldelser 1163371 )
(da) M. Lothaire , Anvendt kombinatorik på ord , Cambridge (GB), Cambridge University Press , koll. "Encyklopædi for matematik og dens anvendelser" ( nr . 105)2005, 610 s. ( ISBN 978-0-521-84802-2 , zbMATH 1133.68067 , læs online )
Michel Gondran og Michel Minoux , grafer, dioider og semi-ringe: nye modeller og algoritmer , Paris, Tec & Doc,2001, xvi + 415 s. ( ISBN 2-7430-0489-4 , SUDOC 060.235.101 )- Engelsk udgave: (en) Michel Gondran og Michel Minoux , Graphs, Dioids and Semirings: New Models and Algorithms , Dordrecht, Springer Science & Business Media, coll. "Operationsforskning / Computer Science Interfaces Series" ( nr . 41)2008, xix + 383 s. ( ISBN 978-0-387-75450-5 , zbMATH 1201,16038 , SUDOC 12874958X , læse online )
(en) Jacques Sakarovitch , Elements of automata theory (Oversat fra fransk af Reuben Thomas) , Cambridge, Cambridge University Press ,2009, 758 s. ( ISBN 978-0-521-84425-3 , zbMATH 1188.68177 )
Manfred Droste og Werner Kuich, "Semirings and Formal Power Series" , i Manfred Droste, Werner Kuich, Heiko Vogler (red.), Handbook of Weighted Automata , Springer-Verlag,2009( DOI 10.1007 / 978-3-642-01492-5_1 ) , s. 3-29
Zoltán Ésik , “Iteration semirings” , i Masami Ito (redaktør), Developments in language theory (12. internationale konference, DLT 2008, Kyoto, Japan, 16. - 19. september 2008) . , Berlin, Springer-Verlag , koll. "Forelæsningsnotater inden for datalogi" ( nr . 5257)2008( ISBN 978-3-540-85779-2 , DOI 10.1007 / 978-3-540-85780-8_1 , zbMATH 1161.68598 ) , s. 1–20
Zoltán Ésik og Werner Kuich , "Equation axioms for a theory of automata" , i Carlos Martín-Vide, Formelle sprog og applikationer , Berlin, Springer-Verlag , koll. "Undersøgelser i uklarhed og blød databehandling" ( nr . 148),2004( ISBN 3-540-20907-7 , zbMATH 1088.68117 ) , s. 183–196
Werner Kuich , “Algebraiske systemer og pushdown automata” , i Werner Kuich, algebraiske fundamenter inden for datalogi. Essays dedikeret til Symeon Bozapalidis i anledning af hans pensionering , Berlin, Springer-Verlag , coll. "Forelæsningsnotater i datalogi" ( nr . 7020)2011( ISBN 978-3-642-24896-2 , zbMATH 1251.68135 ) , s. 228-256.