Jumătate de inel

În matematică , un semi-inel sau semi-inel este o structură algebrică care are următoarele proprietăți: (E,+,×,0,1){\ displaystyle (E, +, \ times, 0,1)}

• (E,+,0){\ displaystyle (E, +, 0)}constituie un monoid comutativ;
• (E,×,1){\ displaystyle (E, \ times, 1)}formează un monoid  ;
• ×{\ displaystyle \ times}este distributiv față de +;
• 0 este absorbant pentru produs, cu alte cuvinte: pentru orice .X∈E:X×0=0×X=0{\ displaystyle x \ în E: x \ times 0 = 0 \ times x = 0}

Aceste proprietăți sunt similare cu cele ale unui inel , diferența fiind că nu există neapărat inversuri pentru adăugarea într-un semicel.

O jumătate de inel este comutativă atunci când produsul său este comutativ; este idempotent atunci când adăugarea sa este idempotentă . Uneori se distinge jumătatea inelelor și jumătatea inelelor unificate  : în acest caz, structura multiplicativă este doar o jumătate de grup , prin urmare nu are neapărat un element neutru. În general, cerem și asta . O jumătate de inel care nu are neapărat un element neutru pentru înmulțire se numește uneori hemi-inel ( hemiring engleză). 0≠1{\ displaystyle 0 \ neq 1}

Contrar a ceea ce se întâmplă pentru inele , nu putem demonstra că 0 este un element absorbant din celelalte axiome.

Domenii de aplicare

Jumătate de inele se găsesc adesea în:

• cercetare operațională  : graficele ponderate au greutăți într-o jumătate de inel; produsul este asociat cu acumularea de valoare de-a lungul unei căi și suma corespunde modului de a compune mai multe căi; calculul celor mai scurte căi este un exemplu particular.
• Teoria limbajelor și a automatelor  : concatenarea (seturilor de) șiruri pentru a-i face pe alții este produsul. Unirea (seturilor de) șiruri este suma;
• teoria locurilor: un loc este o rețea distributivă completă  ; categoria de locuri generalizează , care a spațiilor topologice .

Exemple

Primele exemple

• Cele Numerele naturale formează o jumătate de inel pentru adăugarea și înmulțirea naturală.
• Numere naturale extinse cu adunare și multiplicare extinse și )NU∪{∞}{\ displaystyle \ mathbb {N} \ cup \ {\ infty \}}1=0⋅∞=0{\ displaystyle 1 = 0 \ cdot \ infty = 0}
• Boolean jumătate de inel alcătuit din două elemente 0 și 1. Aceasta este algebra Boolean  : unde și sunt OR și AND respectiv.({0,1},∨,∧,0,1){\ displaystyle (\ {0,1 \}, \ vee, \ wedge, 0,1)}∨{\ displaystyle \ vee}∧{\ displaystyle \ wedge}
• În special, o algebră booleană este o astfel de jumătate de inel. Un inel Boole este, de asemenea, o jumătate de inel - deoarece este un inel - dar adăugarea nu este idempotentă. O jumătate de inel boolean este o jumătate de inel care este izomorfă pentru o sub-jumătate de inel a unei algebre booleene.
• O rețea distributivă este o jumătate de inel comutativă și idempotentă pentru legi și .∨{\ displaystyle \ vee}∧{\ displaystyle \ wedge}
• O rețea într-un inel este o jumătate de inel idempotentă pentru multiplicare și operația definită de .∇{\ displaystyle \ nabla}la∇b=la+b+bla-labla-blab{\ displaystyle a \ nabla b = a + b + ba-aba-bab}
• Setul de idealuri dintr-un inel formează o jumătate de inel pentru adunarea și multiplicarea idealurilor.
• Cele dioids sunt inele și jumătate de persoane.
• Jumătate inelul probabilităților este numere non-negative , reale cu adaos succes și multiplicarea.
• Log jumătate de inel  (in) on cu adaos dat deR∪{±∞}{\ displaystyle \ mathbb {R} \ cup \ {\ pm \ infty \}}

X⊕y=-Buturuga⁡(e-X+e-y) ,{\ displaystyle x \ oplus y = - \ log (e ^ {- x} + e ^ {- y}) \,} iar pentru multiplicare, elementul zero și unitatea elementului .+{\ displaystyle +}+∞{\ displaystyle + \ infty}0{\ displaystyle 0}

• Łukasiewicz jumătate de inel este intervalul închis , cu adaos de și pentru multiplicare . O astfel de jumătate de inel apare în logica polivalentă .[0,1]{\ displaystyle [0,1]}la+b=max(la,b){\ displaystyle a + b = \ max (a, b)}lab=max(0,la+b-1){\ displaystyle ab = \ max (0, a + b-1)}
• Viterbi jumătate de inel este definit pe set , cu adaos dat de maximul și înmulțirea obișnuită; apare în analiza gramaticilor probabilistice .[0,1]{\ displaystyle [0,1]}

Exemple generale

• Setul de părți ale unui set E prevăzut cu uniunea și intersecția este un semicerc. Cele două legi sunt distributive una față de alta, elementul neutru al uniunii este mulțimea goală, cea a intersecției este mulțimea E. Cele două legi sunt comutative și împreună cu E formează cei doi monoizi necesari. Este o algebră booleană și, prin urmare, o rețea .
• Ansamblul relațiilor binare asupra unui set, cu adunarea dată de uniune și multiplicarea prin compoziția relațiilor. Zero-ul acestui jumătate de inel este relația goală, iar elementul său de unitate relația de identitate.
• Setul de limbaje formale pe un alfabet dat este o jumătate de inel cu adaosul dat de uniune și produsul de produsul concatenării elementelor. Zero este setul gol, iar unitatea setul redus la cuvântul gol.
• Mai general, setul de piese ale unui monoid, prevăzut cu îmbinarea și produsul pieselor este un semicerc.U⋅V={tu⋅v∣tu∈U, v∈V}{\ displaystyle U \ cdot V = \ {u \ cdot v \ mid u \ in U, \ v \ in V \}}
• La fel, familia părților unui monoid M cu multiplicități, adică sume formale ale elementelor lui M cu coeficienți întregi naturali formează un semicerc. Adunarea este suma formală cu adunarea coeficienților, iar multiplicarea este produsul Cauchy. Suma zero este elementul neutru pentru adunare și monomul format din elementul neutru al lui M este unitatea pentru multiplicare.

Demi-inel tropical

• Setul de numere naturale extinse la modul obișnuit (orice sumă cu dă  ; orice produs cu dă , cu excepția lui 0 care rămâne absorbant) furnizat cu operatorul min și suma este o jumătate de inel: este cunoscut sub numele de ( min, +) - jumătate și inel tropical , așa numit în onoarea promotorului său Imre Simon . Crearea adjectivului tropical este atribuită de Jean-Éric Pin lui Dominique Perrin, în timp ce Imre Simon însuși o atribuie lui Christian Choffrut. Termenul tropical se referă doar la originile braziliene, deci la tropice, ale lui Imre Simon. Această structură stă la baza algoritmilor pentru calcularea celei mai scurte căi dintr-un grafic: greutățile sunt adăugate de-a lungul căilor și în fața mai multor căi, luăm costul minim. O variantă este (max, +) - jumătate de inel, unde max ia locul min . Ambele sunt inele tropicale.∞{\ displaystyle \ infty}∞{\ displaystyle \ infty}∞{\ displaystyle \ infty}∞{\ displaystyle \ infty}∞{\ displaystyle \ infty}(NU∪{∞},min,+,∞,0){\ displaystyle (\ mathbb {N} \ cup \ {\ infty \}, \ min, +, \ infty, 0)}
• (NU∪{∞},max,min,0,∞){\ displaystyle (\ mathbb {N} \ cup \ {\ infty \}, \ max, \ min, 0, \ infty)} este jumătatea inelului care stă la baza calculului fluxului maxim al unui grafic: într-o succesiune de arce, cea a greutății minime îi impune fluxul și în fața mai multor secvențe, luăm fluxul maxim.

Transferul structurii

Prin transfer de structură  :

• Cele matricelor pătrate de ordinul n cu intrări într - o jumătate de inel și cu adăugarea și înmulțirea indusă; acest semi-inel nu este, în general, comutativ, chiar dacă jumătatea inelului intrărilor sale este.
• Setul End ( A ) al endomorfismelor unui monoid A comutativ este un inel cu jumătate, adițional, cel indus de A ( ) și pentru multiplicare compoziția funcțiilor . Morfismul nul și identitatea sunt elementele neutre.f+g(la)=f(la)+g(la){\ displaystyle f + g (a) = f (a) + g (a)}
• Setul de polinoame cu coeficienți într-un semicel S formează o jumătate de inel, comutativ dacă S este, idempotent dacă S este. Dacă S este setul de numere întregi naturale, acesta este semicelul liber cu generator { x }.S[X]{\ displaystyle S [x]}

Semicerc complet și continuu

Un monoid complet este un monoid comutativ care are o operație de însumare infinită pentru orice set de indici și astfel încât să dețină următoarele proprietăți: ∑Eu{\ displaystyle \ sum _ {I}}Eu{\ displaystyle I}

∑eu∈∅meu=0;∑eu∈{j}meu=mj;∑eu∈{j,k}meu=mj+mkpentruj≠k{\ 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}

și

∑j∈J∑eu∈Eujmeu=∑eu∈Eu(meu)dacă⋃j∈JEuj=EușiEuj∩Euj′=∅pentruj≠j′{\ 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 '}

Un monoid continuu este un monoid ordonat pentru care orice set ordonat de filtrare are o margine superioară care este, de asemenea, compatibilă cu operația monoidă:

la+cinaS=cina(la+S) .{\ displaystyle a + \ sup S = \ sup (a + S) \.}

Cele două concepte sunt strâns legate: un monoid continuu este complet, suma infinită poate fi într-adevăr definită prin:

∑Eulaeu=cina∑Elaeu{\ displaystyle \ sum _ {I} a_ {i} = \ sup \ sum _ {E} a_ {i}}

unde „sup” este preluat pe toate subseturile finite E ale lui I și fiecare însumare, în membrul potrivit, se referă, așadar, la un set finit.

Un semi-inel complet este un semi-inel pentru care monoidul aditiv este un monoid complet și care îndeplinește următoarele legi distributive infinite:

∑eu∈Eu(la⋅laeu)=la⋅(∑eu∈Eulaeu){\ displaystyle \ sum _ {i \ in I} {(a \ cdot a_ {i})} = a \ cdot {\ bigl (} \ sum _ {i \ in I} {a_ {i}} {\ bigl )}}   și   .∑eu∈Eu(laeu⋅la)=(∑eu∈Eulaeu)⋅la{\ displaystyle \ sum _ {i \ in I} {(a_ {i} \ cdot a)} = {\ bigl (} \ sum _ {i \ in I} {a_ {i}} {\ bigl)} \ cdot a}

Un exemplu de jumătate de inel complet este setul de părți ale unui monoid pentru unire; jumătatea inelului intrării moare într-o jumătate de inel completă este în sine o jumătate de inel completă.

O jumătate de inel continuă este un monoid continu a cărui multiplicare respectă ordinea și limitele superioare. Jumătatea-ring N ∪ {∞} cu adaos, înmulțirea și ordinea naturală este un proces continuu de jumătate de inel.

Orice jumătate de inel continuu este completă și această proprietate poate fi inclusă în definiție.

Jumătate de inel stea

Un semi-inel stelar (în engleză star semiring sau starsemiring este un semionator prevăzut cu un operator suplimentar unar notat „*” satisfăcător:

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

Exemple de jumătăți de inele stelare:

• Semicelul lui Boole cu 0 ∗ = 1 ∗ = 1 ;
• Jumătatea inelul de relații binare pe un set de U , unde vedeta unei relații R este definit de

R∗=⋃nu≥0Rnu{\ displaystyle R ^ {*} = \ bigcup _ {n \ geq 0} R ^ {n}}. Aceasta este închiderea reflexivă și tranzitivă a relației R .

• Inelul de jumătate al limbajelor formale este un inel de jumătate de stea complet, operația stelară fiind steaua lui Kleene .
• Setul de numere reale pozitive a crescut cu ∞, cu adunarea și înmulțirea obișnuită este o jumătate de inel complet a stelei cu operația stea dată de a ∗ = 1 / (1 - a ) pentru 0 ≤ a <1 ( seria geometrică obișnuită ) și a ∗ = ∞ pentru a ≥ 1 .
• Jumătatea inelul N ∪ {∞}, cu adaos extins și înmulțire și 0 * = 1 , o * = ∞ pentru a ≥ 1 .

Algebra Kleene

O algebră Kleene este un inel înstelat cu adaos idempotent; intervin în teoria limbajului și în expresii regulate .

Half Ring Conway

Un semi-inel Conway este un semi-inel în formă de stea care satisface următoarele ecuații între operația stelei și adunarea și multiplicarea:

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

Primele trei exemple de mai sus sunt, de asemenea, jumătăți de inele Conway.

Semiteriu iterativ

O jumătate de inerare iterativă ( semiterare în iterație engleză ) Conway este o jumătate de inel din care verifică grupurile de axiome Conway asociate grupurilor John Conway în jumătatea inelelor cu stea

Inel de jumătate de stea completă

O jumătate de inel de stea completă este o jumătate de inel în care steaua are proprietățile obișnuite ale stelei lui Kleene  ; îl definim folosind operatorul de sumare infinită prin:

la∗=∑j≥0laj{\ displaystyle a ^ {*} = \ sum _ {j \ geq 0} {a ^ {j}}}

cu și pentru . la0=1{\ displaystyle a ^ {0} = 1}laj+1=la⋅laj=laj⋅la{\ displaystyle a ^ {j + 1} = a \ cdot a ^ {j} = a ^ {j} \ cdot a}j≥0{\ displaystyle j \ geq 0}

Semicirculele relațiilor binare, limbajelor formale și numerelor reale extinse non-negative sunt cu stea completă.

Un inel de jumătate de stea complet este, de asemenea, un inel de jumătate de Conway, dar inversul nu este adevărat. Un exemplu este oferit de numerele raționale extinse non-negative , cu adunarea obișnuită și multilicație. {X∈Î∣X≥0}∪{∞}{\ displaystyle \ {x \ in \ mathbb {Q} \ mid x \ geq 0 \} \ cup \ {\ infty \}}

Note și referințe

1. Golan 1999 , p.  1.
2. Sakarovich 2009 , p.  28.
3. Alexander E. Guterman, „Rank and determinant functions for matrices over semirings” , în Nicholas Young și Yemon Choi (eds), Surveys in Contemporary Mathematics , Cambridge University Press , col.  „London Mathematical Society Note Play Series” ( nr .  347)2008( ISBN  0-521-70564-9 , zbMATH  1181.16042 ) , p.  1–33.
4. Lothaire 2005 , p.  211.
5. Claude Pair, „Despre algoritmi pentru probleme de flux în grafice finite” , în P. Rosentiehl, Théorie des graphes (zile de studiu internaționale) - Teoria graficelor (simpozion internainal) , Dunod (Paris) și Gordon și Breach (Nou York),1966
6. Droste și Kuich 2009 , p.  7-10.
7. Berstel și Reutenauer 2011 , p.  4.
8. Jean-Éric Pin, „Tropical Semirings” , în J. Gunawardena , Idempotency (Bristol, 1994) , Cambridge, Cambridge University Press, col.  „Publ. Newton Inst. 11  ”, 1998 ,, p.  50-69 .
9. Imre Simon, „Seturi recunoscute cu multiplicități în semiremiile tropicale” , în Mathematical Foundations of Computer Science (Carlsbad, 1988) , Springer, col.  „Note de curs în informatică” ( nr .  324), 1988( citiți online ) , p.  107-120.
10. Mathoverflow, 2011, Ce este tropical la algebra tropicală? pe Mathoverflow
11. Udo Hebisch , "  Eine algebraische Theorie unendlicher Summen mit Anwendungen auf Halbgruppen und Halbringe  ", Bayreuther Mathematische Schriften , vol.  40,1992, p.  21–152 ( zbMATH  0747.08005 )
12. Werner Kuich , „ ir -semirings continue, sisteme algebrice și pushdown automates” , în Michael S. Paterson (editor), Automata, Limbaje și programare (17 International Colloquium, Universitatea Warwick, Anglia, 16-20 iulie , 1990) , Springer-Verlag , col.  „Note de curs în informatică” ( nr .  443), 1990( ISBN  3-540-52826-1 ) , p.  103-110
13. Kuich 2011 .
14. Sakarovich 2009 , p.  471.
15. Zoltán Ésik și Hans Leiß , „Greibach normal form in algebraically complete semirings” , în Julian Bradfield, Computer Science Logic (al 16-lea atelier internațional, CSL 2002, a 11-a conferință anuală a EACSL, Edinburgh, Scoția, 22-25 septembrie 2002) , Berlin, Springer-Verlag , col.  „Note de curs în informatică” ( nr .  2471), 2002( zbMATH  1020.68056 ) , p.  135-150.
16. Esik 2008 .
17. Daniel J. Lehmann, „  Structuri algebrice pentru închidere tranzitivă  ”, Theoretical Computer Science , vol.  4, n o  1,1977, p.  59-76.
18. Berstel și Reutenauer 2011 , p.  27.
19. Esik și Kuich 2004 .
20. John H. Conway , Algebră regulată și mașini finite , Londra, Chapman și Hall,1971( ISBN  0-412-10620-5 , zbMATH  0231.94041 )
21. Droste și Kuich 2009 , Teorema 3.4 p.  15 .

Bibliografie

• Claude Pair, „Despre algoritmi pentru probleme de flux în grafice finite” , în P. Rosentiehl, Théorie des graphes (zile de studiu internaționale) - Teoria graficelor (simpozion internainal) , Dunod (Paris) și Gordon and Breach (New York),1966
• Jean Claude Derniame și Claude Pair, Probleme de progresie în grafice , Dunod (Paris),1971, 182  p.
• Kazimierz Głazek , Un ghid pentru literatura despre semirings și aplicațiile lor în matematică și științele informației. Cu bibliografie completă , Dordrecht, Kluwer Academic,2002( ISBN  1-4020-0717-5 , zbMATH  1072.16040 )
• Jonathan S. Golan, Semirings and their Applications , Dordrecht, Kluwer Academic Publishers (Springer Science & Business Media),1999, xii + 381  p. ( ISBN  978-0-7923-5786-5 , Math Reviews  1746739 , citiți online )- Ediția revizuită și extinsă a (ro) Teoria semirings, cu aplicații la matematică și informatică teoretică , Harlow, Longman Scientific & Technical și John Wiley & Sons, col.  „Monografii și sondaje Pitman în matematică pură și aplicată”,1992, xiv + 318  p. ( ISBN  0-582-07855-5 , Recenzii matematice  1163371 )
• (ro) M. Lothaire , Combinatorie aplicată pe cuvinte , Cambridge (GB), Cambridge University Press , col.  "Enciclopedia matematicii și a aplicațiilor sale" ( nr .  105)2005, 610  p. ( ISBN  978-0-521-84802-2 , zbMATH  1133.68067 , citit online )
• Michel Gondran și Michel Minoux , Grafice, dioide și semi-inele: noi modele și algoritmi , Paris, Tec & Doc,2001, xvi + 415  p. ( ISBN  2-7430-0489-4 , SUDOC  060235101 )- Ediția în limba engleză: (ro) Michel Gondran și Michel Minoux , Grafice, dioxide și semirings: noi modele și algoritmi , Dordrecht, Springer Science & Business Media, col.  "Seria de interfețe de cercetare operațională / informatică" ( nr .  41)2008, xix + 383  p. ( ISBN  978-0-387-75450-5 , zbMATH  1201.16038 , SUDOC  12874958X , citiți online )
• (en) Jacques Sakarovitch , Elements of automata theory (Traducere din franceză de Reuben Thomas) , Cambridge, Cambridge University Press ,2009, 758  p. ( ISBN  978-0-521-84425-3 , zbMATH  1188.68177 )
• Manfred Droste și Werner Kuich, „Semirings and Formal Power Series” , în Manfred Droste, Werner Kuich, Heiko Vogler (eds), Handbook of Weighted Automata , Springer-Verlag,2009( DOI  10.1007 / 978-3-642-01492-5_1 ) , p.  3-29
• Zoltán Ésik , „Iteration semirings” , în Masami Ito (editor), Developments in language theory (a 12-a conferință internațională, DLT 2008, Kyoto, Japonia, 16-19 septembrie 2008) . , Berlin, Springer-Verlag , col.  „Note de curs în informatică” ( nr .  5257)2008( ISBN  978-3-540-85779-2 , DOI  10.1007 / 978-3-540-85780-8_1 , zbMATH  1161.68598 ) , p.  1-20
• Zoltán Ésik și Werner Kuich , „ Axiome ecuaționale pentru o teorie a automatelor” , în Carlos Martín-Vide, Limbaje și aplicații formale , Berlin, Springer-Verlag , col.  „Studii în Fuzziness și Soft Computing” ( nr .  148),2004( ISBN  3-540-20907-7 , zbMATH  1088.68117 ) , p.  183–196
• Werner Kuich , „Sisteme algebrice și automate pushdown” , în Werner Kuich, Fundamente algebrice în informatică. Eseuri dedicate lui Symeon Bozapalidis cu ocazia pensionării sale , Berlin, Springer-Verlag , col.  „Note de curs în informatică” ( nr .  7020)2011( ISBN  978-3-642-24896-2 , zbMATH  1251.68135 ) , p.  228–256.

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">