Poloviční prsten

V matematiky , je polovina-kruh , nebo semi-kroužek , je algebraická struktura , která má následující vlastnosti: (E,+,×,0,1){\ displaystyle (E, +, \ krát, 0,1)}

• (E,+,0){\ displaystyle (E, +, 0)}představuje komutativní monoid ;
• (E,×,1){\ displaystyle (E, \ krát, 1)}tvoří monoid  ;
• ×{\ displaystyle \ times}je distribuční vzhledem k +;
• 0 je absorpční pro produkt, jinými slovy: pro všechno .X∈E:X×0=0×X=0{\ displaystyle x \ v E: x \ krát 0 = 0 \ krát x = 0}

Tyto vlastnosti jsou podobné vlastnostem prstenu , rozdíl je v tom, že pro přidání do půlkruhu nemusí být nutně inverze.

Půlkruh je komutativní, když je jeho produkt komutativní; je idempotentní, když je jeho přidání idempotentní . Někdy se rozlišují půlkruhy a sjednocené půlkruhy  : v tomto případě je multiplikativní struktura pouze poloviční skupinou , a proto nemusí nutně mít neutrální prvek. Obecně to také žádáme . Poloviční prsten, který nemusí nutně mít neutrální prvek pro množení, se někdy nazývá hemi-ring ( hemiring anglicky). 0≠1{\ displaystyle 0 \ neq 1}

Na rozdíl od toho, co se stane u prstenů , nemůžeme dokázat, že 0 je absorbující prvek z ostatních axiomů.

Oblasti použití

Polokroužky se často nacházejí v:

• operační výzkum  : vážené grafy mají váhy v půlkruhu; produkt je spojen s akumulací hodnoty podél cesty a součet odpovídá způsobu skládání několika cest; konkrétním příkladem je výpočet nejkratších cest .
• Teorie jazyků a automatů  : produktem je zřetězení (sad) řetězců za účelem vytváření dalších. Spojení (sad) řetězců je součet;
• teorie míst: místo je úplná distribuční mřížka  ; kategorie míst zobecňuje to topologických prostorů .

Příklady

První příklady

• Tyto přirozená čísla tvoří polovinu-kroužek pro sčítání a násobení přirozené.
• Rozšířená přirozená čísla s rozšířeným sčítáním a násobením a )NE∪{∞}{\ displaystyle \ mathbb {N} \ pohár \ {\ infty \}}1=0⋅∞=0{\ displaystyle 1 = 0 \ cdot \ infty = 0}
• Logická poloviny-kroužek sestává ze dvou prvků, 0 a 1. To je booleovské algebry  : kde a jsou OR a A v tomto pořadí.({0,1},∨,∧,0,1){\ displaystyle (\ {0,1 \}, \ vee, \ klín, 0,1)}∨{\ displaystyle \ vee}∧{\ displaystyle \ klín}
• Zejména booleovská algebra je takový půlkruh. Boole kroužek je také poloviční prstenec - protože se jedná o prsten - ale přidání není idempotent. Booleovská poloviny-kroužek je polovina-kroužek, který je izomorfní s dílčí půl kruhu booleovské algebry.
• Distributivní svaz je komutativní half-ring a idempotent pro zákony a .∨{\ displaystyle \ vee}∧{\ displaystyle \ klín}
• Mříž v kruhu je půlkruh idempotentní pro násobení a operaci definovanou .∇{\ displaystyle \ nabla}na∇b=na+b+bna-nabna-bnab{\ displaystyle a \ nabla b = a + b + ba-aba-bab}
• Sada ideálů v kruhu tvoří půlkruh pro sčítání a množení ideálů.
• Tyto dioids jsou polokroužků jednotlivci.
• Poloviny kroužku pravděpodobností je nezáporná reálná čísla s neúspěšné sčítání a násobení.
• Log poloviny-kroužek  (v) na s přídavkem danouR∪{±∞}{\ displaystyle \ mathbb {R} \ pohár \ {\ pm \ infty \}}

X⊕y=-log⁡(E-X+E-y) ,{\ displaystyle x \ oplus y = - \ log (e ^ {- x} + e ^ {- y}) \,} a pro násobení prvek nula a jednotka prvku .+{\ displaystyle +}+∞{\ displaystyle + \ infty}0{\ displaystyle 0}

• Łukasiewiczův půlkruh je uzavřený interval , s pro sčítání a pro násobení . Takový půlkruh se objevuje v polyvalentní logice .[0,1]{\ displaystyle [0,1]}na+b=max(na,b){\ displaystyle a + b = \ max (a, b)}nab=max(0,na+b-1){\ displaystyle ab = \ max (0, a + b-1)}
• Viterbiho půlkruh je definován na množině , sčítání je dáno maximem a obvyklým násobením; objevuje se v analýze pravděpodobnostních gramatik .[0,1]{\ displaystyle [0,1]}

Obecné příklady

• Sada částí sady E opatřená spojkou a průsečíkem je půlkruh. Tyto dva zákony jsou distribuční vůči sobě navzájem, neutrálním prvkem unie je prázdná množina, křižovatkou je množina E. Tyto dva zákony jsou komutativní a společně s E tvoří dva požadované monoidy. Je to booleovská algebra, a proto mřížka .
• Sada binárních vztahů na množině s přídavkem daným sjednocením a vynásobením složením vztahů. Nula tohoto půlkruhu je prázdný vztah a jeho jednotkovým prvkem je vztah identity.
• Sada formálních jazyků na dané abecedě je půlkruh s přídavkem daným unií a součinem součinem zřetězení prvků. Nula je prázdná množina a jednota množiny redukovaná na prázdné slovo.
• Obecněji řečeno, sada částí monoidu, opatřená spojením a produktem částí, je půlkruh.U⋅PROTI={u⋅proti∣u∈U, proti∈PROTI}{\ displaystyle U \ cdot V = \ {u \ cdot v \ mid u \ v U, \ v \ ve V \}}
• Podobně rodina částí monoidu M s multiplicitami, to znamená formální součty prvků M s přirozenými celočíselnými koeficienty, tvoří půlkruh. Sčítání je formální součet s přidáním koeficientů a násobení je Cauchyův součin. Nulový součet je neutrální prvek pro sčítání a monom vytvořený z neutrálního prvku M je jednotka pro násobení.

Tropický půlkruh

• Sada přirozených čísel rozšířená na obvyklým způsobem (libovolný součet s dává  ; jakýkoli součin s dává , s výjimkou 0, která zůstává pohlcující) poskytovaná operátorem min a součet je půlkruh: je známý pod jmény de ( min, +) - tropický půlkruh a půlkruh , pojmenovaný na počest jeho promotéra Imre Simona . Vytvoření adjektiva tropické připisuje Jean-Éric Pin Dominique Perrinovi, zatímco sám Imre Simon jej připisuje Christianovi Choffrutovi. Termín tropický odkazuje pouze na brazilský původ, tedy na tropy, Imre Simona. Tato struktura je základem algoritmů pro výpočet nejkratší cesty v grafu: váhy se přidávají podél cest a před několika cestami bereme minimální náklady. Varianta je (max, +) - půlkruh, kde max nahrazuje min . Oba jsou tropické půlkruhy.∞{\ displaystyle \ infty}∞{\ displaystyle \ infty}∞{\ displaystyle \ infty}∞{\ displaystyle \ infty}∞{\ displaystyle \ infty}(NE∪{∞},min,+,∞,0){\ displaystyle (\ mathbb {N} \ pohár \ {\ infty \}, \ min, +, \ infty, 0)}
• (NE∪{∞},max,min,0,∞){\ displaystyle (\ mathbb {N} \ pohár \ {\ infty \}, \ max, \ min, 0, \ infty)} je polokroužek, který je základem pro výpočet maximálního toku grafu: v posloupnosti oblouků ukládá tok minimální váha a před několika sekvencemi vezmeme maximální tok.

Přenos struktury

Převodem struktury  :

• Tyto čtvercové matice z řádu n se vstupy v půl kruhu a s přídavkem a násobení indukované; tento půlkruh není obecně komutativní, i když půlkruh jeho vstupů ano.
• Množina End ( A ) endomorfismů komutativního monoidu A je půlkruh, který je navíc indukován A ( ) a pro násobení složení funkcí . Nulový morfismus a identita jsou neutrálními prvky.F+G(na)=F(na)+G(na){\ displaystyle f + g (a) = f (a) + g (a)}
• Sada polynomů s koeficienty v půlkruhu S tvoří půlkruh, komutativní, pokud S je, idempotentní, pokud S je. Pokud S je množina přirozených celých čísel, jedná se o volný půlkruh s generátorem { x }.S[X]{\ displaystyle S [x]}

Plný a nepřetržitý půlkruh

Kompletní Monoid je komutativní monoid, který má nekonečný operaci sumační pro každý soubor indexů a tak, že tyto vlastnosti platí: ∑Já{\ displaystyle \ sum _ {I}}Já{\ displaystyle I}

∑i∈∅mi=0;∑i∈{j}mi=mj;∑i∈{j,k}mi=mj+mkproj≠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}

a

∑j∈J∑i∈Jájmi=∑i∈Já(mi)-li⋃j∈JJáj=JáaJáj∩Jáj′=∅proj≠j′{\ displaystyle \ sum _ {j \ v J} {\ sum _ {i \ v I_ {j}} {m_ {i}}} = \ sum _ {i \ v I} (m_ {i}) \; {\ textrm {si}} \ bigcup _ {j \ in J} I_ {j} = I \; {\ textrm {and}} \; I_ {j} \ cap I_ {j '} = \ emptyset \; { \ textrm {pro}} \; j \ neq j '}

Kontinuální Monoid je uspořádaná monoid pro nějž filtrování uspořádaná množina má horní hranici , která je navíc kompatibilní s monoid provozu:

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

Oba pojmy spolu úzce souvisejí: spojitý monoid je kompletní, nekonečný součet lze definovat:

∑Jánai=sup∑Enai{\ displaystyle \ sum _ {I} a_ {i} = \ sup \ sum _ {E} a_ {i}}

kde „sup“ je převzat ze všech konečných podmnožin E z I a každý součet v pravém členu tedy souvisí s konečnou množinou.

Kompletní půlkruh je půlkruh, pro který je aditivní monoid úplným monoidem a který splňuje následující nekonečné distributivní zákony:

∑i∈Já(na⋅nai)=na⋅(∑i∈Jánai){\ displaystyle \ sum _ {i \ in I} {(a \ cdot a_ {i})} = a \ cdot {\ bigl (} \ sum _ {i \ in I} {a_ {i}} {\ bigl )}}   a   .∑i∈Já(nai⋅na)=(∑i∈Jánai)⋅na{\ displaystyle \ sum _ {i \ v I} {(a_ {i} \ cdot a)} = {\ bigl (} \ sum _ {i \ v I} {a_ {i}} {\ bigl)} \ cdot a}

Příkladem úplného půlkruhu je sada částí monoidu pro unii; půlkruh vstupních matric v úplném půlkruhu je sám o sobě úplným polokroužkem.

Kontinuální poloviny-kroužek je kontinuální monoid jehož násobení respektuje řád a horní hranice. Půlprstenec N ∪ {∞} s přídavkem, násobení a přirozeného řádu je kontinuální poloviny-kroužek.

Jakýkoli spojitý půlkruh je úplný a tuto vlastnost lze zahrnout do definice.

Hvězdný půlkruh

Hvězda semiring (v angličtině hvězdy semiring nebo starsemiring je polovina-kroužek opatřen přídavným unární poznamenat, „*“ uspokojivé:

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

Příklady půlkruhů hvězd:

• Půlkruh Boole s 0 ∗ = 1 ∗ = 1 ;
• Polokruh binárních relací na množině U , kde je hvězda relace R definována

R∗=⋃ne≥0Rne{\ displaystyle R ^ {*} = \ bigcup _ {n \ geq 0} R ^ {n}}. To je reflexivní a tranzitivní uzávěr podle vztahu R .

• Půlkruh formálních jazyků je úplným půlhvězdným prstencem, přičemž hvězdnou operací je Kleeneova hvězda .
• Množina kladných reálných čísel se zvýšil o ∞, s obvyklým sčítání a násobení je kompletní hvězda poloviny-kroužek hvězdy provozu dané v * = 1 / (1 - a ) na 0? A <1 (v obvyklém geometrická řada ) a * = ∞ pro ≥ 1 .
• Půlprstenec N ∪ {∞}, s prodlouženou sčítání a násobení a 0 * = 1 , * = ∞ pro ≥ 1 .

Kleene algebra

Kleene algebry je hvězdné poloviny-kroužek s přídavkem idempotentních; podílejí se na teorii jazyků a na regulárních výrazech .

Poloviční Conway Ring

Conway poloviny-kroužek je ve tvaru hvězdy poloviny-kroužek, který splňuje následující rovnice mezi hvězdy provozu a sčítání a násobení:

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

První tři výše uvedené příklady jsou také poloviční Conwayovy kroužky.

Iterativní půlkruh

Poloviny-kroužek iterativní (anglicky iteraci semiring ) Conway je polovina-kruh, který kontroluje Conway axiómy skupiny spojené od John Conway skupin polokroužků hvězdičkou

Plný hvězdný půlkruh

Full hvězda half-ring je polovina-ring, kde hvězda má obvyklé vlastnosti z Kleenova hvězdy  ; definujeme jej pomocí operátoru nekonečného součtu pomocí:

na∗=∑j≥0naj{\ displaystyle a ^ {*} = \ součet _ {j \ geq 0} {a ^ {j}}}

s a pro . na0=1{\ displaystyle a ^ {0} = 1}naj+1=na⋅naj=naj⋅na{\ displaystyle a ^ {j + 1} = a \ cdot a ^ {j} = a ^ {j} \ cdot a}j≥0{\ displaystyle j \ geq 0}

Polokruhy binárních vztahů, formálních jazyků a rozšířených nezáporných reálných čísel jsou plně označeny hvězdičkou.

Kompletní půlhvězdičkový prsten je také půlkruhový prsten Conway, ale obrácení není pravda. Příkladem jsou rozšířená nezáporná racionální čísla s obvyklým sčítáním a násobením. {X∈Q∣X≥0}∪{∞}{\ displaystyle \ {x \ v \ mathbb {Q} \ střední x \ geq 0 \} \ pohár \ {\ infty \}}

Poznámky a odkazy

1. Golan 1999 , str.  1.
2. Sakarovich 2009 , s.  28.
3. Alexander E. Guterman, „Pořadí a určující funkce pro matice nad semestry“ , Nicholas Young a Yemon Choi (eds), Průzkumy současné matematiky , Cambridge University Press , kol.  "Londýn matematická společnost Pozn Play Series" ( n o  347)2008( ISBN  0-521-70564-9 , zbMATH  1181.16042 ) , s.  1–33.
4. Lothaire 2005 , str.  211.
5. Claude Pair, „O algoritmech pro problémy toku v konečných grafech“ , v P. Rosentiehl, Théorie des graphes (mezinárodní studijní dny) - Theory of Graphs (internainal symposium) , Dunod (Paris) and Gordon and Breach (New York),1966
6. Droste a Kuich 2009 , s.  7-10.
7. Berstel a Reutenauer 2011 , s.  4.
8. Jean-Éric Pin, „Tropical Semirings“ , J. Gunawardena, Idempotency (Bristol, 1994) , Cambridge, Cambridge University Press, kol.  „Publ. Newton Inst. 11  ”, 1998, s.  50-69 .
9. Imre Simon, „Rozpoznatelné množiny s multiplicitou v tropickém semiringu“ , Mathematical Foundations of Computer Science (Carlsbad, 1988) , Springer, kol.  "Lecture Notes in Computer Science" ( n O  324), 1988( číst online ) , s.  107–120.
10. Mathoverflow, 2011, Co je tropické na tropické algebře? na Mathoverflow
11. Udo Hebisch , „  Eine algebraische Theorie unendlicher Summen mit Anwendungen auf Halbgruppen und Halbringe  “, Bayreuther Mathematische Schriften , sv.  40,1992, str.  21–152 ( zbMATH  0747.08005 )
12. Werner Kuich , „ω-spojité semirings, algebraické systémy a pushdown automaty“ , Michael S. Paterson (editor), Automata, Languages ​​and Programming (17. mezinárodní kolokvium, Warwick University, Anglie, 16. – 20. Července , 1990) , Springer-Verlag , kol.  "Lecture Notes in Computer Science" ( n O  443), 1990( ISBN  3-540-52826-1 ) , str.  103–110
13. Kuich 2011 .
14. Sakarovič 2009 , s.  471.
15. Zoltán Ésik a Hans Leiß , „Greibachova normální forma v algebraicky úplných seminářích“ , Julian Bradfield, Computer Science Logic (16. mezinárodní workshop, CSL 2002, 11. výroční konference EACSL, Edinburgh, Skotsko, 22. – 25. Září 2002) , Berlín, Springer-Verlag , kol.  "Lecture Notes in Computer Science" ( n O  2471), 2002( zbMATH  1020.68056 ) , s.  135–150.
16. Esik 2008 .
17. Daniel J. Lehmann, „  Algebraické struktury pro tranzitivní uzavření  “, Theoretical Computer Science , sv.  4, n o  1,1977, str.  59-76.
18. Berstel a Reutenauer 2011 , s.  27.
19. Esik a Kuich 2004 .
20. John H. Conway , Pravidelná algebra a konečné stroje , Londýn, Chapman a Hall,1971( ISBN  0-412-10620-5 , zbMATH  0231.94041 )
21. Droste a Kuich 2009 , Věta 3,4 s.  15 .

Bibliografie

• Claude Pair, „O algoritmech pro problémy toku v konečných grafech“ , P. Rosentiehl, Théorie des graphes (mezinárodní studijní dny) - Theory of Graphs (Internainal Symposium) , Dunod (Paříž) a Gordon and Breach (New York),1966
• Jean Claude Derniame a Claude Pair, Problémy postupu v grafech , Dunod (Paříž),1971, 182  s.
• Kazimierz Głazek , Průvodce literaturou o semirings a jejich aplikacích v matematice a informačních vědách. S kompletní bibliografií , 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  str. ( ISBN  978-0-7923-5786-5 , Math Reviews  1746739 , číst online )- Přepracované a rozšířené vydání (en) The theory of semirings, with applications to mathematics and theory computer science , Harlow, Longman Scientific & Technical and John Wiley & Sons, coll.  "Pitmanovy monografie a průzkumy v čisté a aplikované matematice",1992, xiv + 318  str. ( ISBN  0-582-07855-5 , Math Reviews  1163371 )
• (en) M. Lothaire , Aplikovaná kombinatorika slov , Cambridge (GB), Cambridge University Press , kol.  "Encyclopedia of matematiky a její aplikace" ( n o  105)2005, 610  str. ( ISBN  978-0-521-84802-2 , zbMATH  1133,68067 , číst online )
• Michel Gondran a Michel Minoux , Graphs, dioids and semi-ring: new models and algorithms , Paris, Tec & Doc,2001, xvi + 415  str. ( ISBN  2-7430-0489-4 , SUDOC  060235101 )- Anglické vydání: (en) Michel Gondran a Michel Minoux , Graphs, Dioids and Semirings: New Models and Algorithms , Dordrecht, Springer Science & Business Media, coll.  „Operační výzkum / Výpočetní technika rozhraní série“ ( n o  41)2008, xix + 383  str. ( ISBN  978-0-387-75450-5 , zbMATH  1201.16038 , SUDOC  12874958X , číst online )
• (en) Jacques Sakarovitch , Elements of automata theory (přeložil Reuben Thomas z francouzštiny) , Cambridge, Cambridge University Press ,2009, 758  s. ( ISBN  978-0-521-84425-3 , zbMATH  1188,68177 )
• Manfred Droste a Werner Kuich, „Semirings and Formal Power Series“ , Manfred Droste, Werner Kuich, Heiko Vogler (eds), Handbook of Weighted Automata , Springer-Verlag,2009( DOI  10.1007 / 978-3-642-01492-5_1 ) , s.  3-29
• Zoltán Ésik , „Iterační semirings“ , v Masami Ito (editor), Vývoj v teorii jazyků (12. mezinárodní konference, DLT 2008, Kjóto, Japonsko, 16. – 19. Září 2008) . , Berlín, Springer-Verlag , kol.  "Lecture Notes in Computer Science" ( n o  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 a Werner Kuich , „Equational axioms for a theory of automata“ , Carlos Martín-Vide, Formální jazyky a aplikace , Berlín, Springer-Verlag , kol.  „Studies in zmatenost a Soft Computing“ ( n o  148),2004( ISBN  3-540-20907-7 , zbMATH  1088.68117 ) , s.  183–196
• Werner Kuich , „Algebraické systémy a pushdown automaty“ , Werner Kuich, Algebraické základy počítačové vědy. Eseje věnované Symeonovi Bozapalidisovi u příležitosti jeho odchodu do důchodu , Berlín, Springer-Verlag , kol.  "Lecture Notes in Computer Science" ( n o  7020)2011( ISBN  978-3-642-24896-2 , zbMATH  1251,68135 ) , s.  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;">