Zdarma monoid - Free monoid

V algebře je volný monoid v sadě je monoid , jejíž prvky jsou všechny konečné sekvence (nebo řetězce) z nula nebo více prvků z této sady, s zřetězením řetězce jako monoidu provozu a s jedinečnou sekvencí nulových prvků, často zavolal prázdný řetězec a označil je jako prvek identity ε nebo λ . Volný monoid na množině A se obvykle označuje A ^∗ . Bez pologrupa na A je nižší než pologrupa z A ^* obsahuje všechny prvky, kromě prázdného řetězce. Obvykle se označuje A ⁺ .

Obecněji je abstraktní monoid (nebo poloskupina) S popsán jako volný, pokud je na některé množině izomorfní s volným monoidem (nebo poloskupinou).

Jak název napovídá, volné monoidy a poloskupiny jsou ty objekty, které splňují obvyklou univerzální vlastnost definující volné objekty v příslušných kategoriích monoidů a poloskupin. Z toho vyplývá, že každý monoid (nebo poloskupina) vzniká jako homomorfní obraz volného monoidu (nebo poloskupiny). Studium poloskupin jako obrazů volných poloskupin se nazývá kombinatorická teorie poloskupin.

Volné monoidy (a monoidy obecně) jsou podle definice asociativní ; to znamená, že jsou psány bez závorek, které ukazují seskupení nebo pořadí operací. Neasociativním ekvivalentem je volné magma .

Příklady

Přirozená čísla

Přidaný monoid ( N ₀ , +) přirozených čísel (včetně nuly) je volný monoid na generátoru bez singletonu, v tomto případě přirozeného čísla 1. Podle formální definice se tento monoid skládá ze všech sekvencí jako „1 "," 1 + 1 "," 1 + 1 + 1 "," 1 + 1 + 1 + 1 "atd., Včetně prázdné sekvence. Mapování každé takové posloupnosti na její výsledek vyhodnocení a prázdná posloupnost na nulu vytváří izomorfismus ze sady takových posloupností na N ₀ . Tato izomorfismus je kompatibilní s „+“, to znamená, že pro jakékoli dvě sekvence s jsou a t , pokud s je mapován (tedy hodnoceno) s číslem m a t o n , pak jejich zřetězení s + t je mapována na součet m + n .

Kleene hvězda

V teorii formálního jazyka se obvykle uvažuje o konečné sadě „symbolů“ A (někdy nazývaných abeceda). Konečná posloupnost symbolů je nazýván „slovo nad A “ a volný monoid ^* se nazývá „ Kleene hvězda of A “. Takže abstraktní studium formálních jazyků lze považovat za studium podmnožin konečně generovaných volných monoidů.

Například za předpokladu, že abeceda A = { a , b , c }, její Kleeneova hvězda A ^∗ obsahuje všechna zřetězení a , b a c :

{ε, a , ab , ba , caa , cccbabbc , ...}.

Pokud je A libovolná množina, funkce délky slova na A ^∗ je jedinečný monomorfní monoid od A ^∗ do ( N ₀ , +), který mapuje každý prvek A na 1. Volný monoid je tedy odstupňovaným monoidem . (Klasifikovaný monoid je monoid, který lze zapsat jako . Každý je známkou; známkování je zde pouze délka řetězce. To znamená, že obsahuje tyto řetězce délky . Symbol zde může být chápán jako „množinová unie“; používá se místo symbolu, protože množinové odbory obecně nemusí být monoidy, a proto se používá odlišný symbol. Podle konvence jsou gradace vždy psány se symbolem.) ${\ displaystyle M}$${\ displaystyle M = M_ {0} \ oplus M_ {1} \ oplus M_ {2} \ cdots}$${\ displaystyle M_ {n}}$${\ displaystyle M_ {n}}$${\ displaystyle n.}$${\ displaystyle \ oplus}$${\ displaystyle \ cup}$${\ displaystyle \ oplus}$

Mezi teorií pologrup a teorií automatů existuje hluboká souvislost . Například každý formální jazyk má syntaktický monoid, který tento jazyk rozpoznává. V případě běžného jazyka je tento monoid isomorfní s přechodovým monoidem spojeným s poloautomatem nějakého deterministického konečného automatu, který tento jazyk rozpoznává. Pravidelné jazyky nad abecedou A jsou uzavření konečných podmnožin A *, volného monoidu nad A, v rámci sjednocení, součinu a generování submonoidu.

V případě souběžného výpočtu , tj. Systémů se zámky , mutexy nebo spojením vláken , lze výpočet popsat pomocí historických monoidů a trasovacích monoidů . Zhruba řečeno, prvky monoidu mohou dojíždět (např. Různá vlákna mohou být spouštěna v jakémkoli pořadí), ale pouze po zámek nebo mutex, které brání dalšímu dojíždění (např. Serializovat přístup vlákna k nějakému objektu).

Konjugovaná slova

Příklad pro 1. případ ekvidivovatelnosti: m = "UNCLE", n = "ANLY", p = "UN", q = "CLEANLY" a s = "CLE"

Definujeme dvojici slov v A ^∗ tvaru uv a vu jako konjugát : konjugáty slova jsou tedy jeho kruhovými posuny . Dvě slova jsou konjugát v tomto smyslu, jsou-li konjugát ve smyslu teorii skupiny jako prvky volné skupiny generované A .

Equidivisibility

Volný monoid je ekvidivovatelný : pokud platí rovnice mn = pq , pak existuje s takové, že buď m = ps , sn = q (příklad viz obrázek) nebo ms = p , n = sq . Tento výsledek je také známý jako Leviho lemma .

Monoid je zdarma, právě když je klasifikovaný a rovnocenný.

Zdarma generátory a hodnocení

Členům množiny A se říká volné generátory pro A ^∗ a A ⁺ . Horní index * se pak běžně chápe jako Kleeneova hvězda . Obecněji řečeno, pokud S je abstraktní volný monoid (semigroup), pak se sada prvků, která se mapuje na sadu jednopísmenných slov pod izomorfismem na semigroup A ⁺ (monoid A ^∗ ), nazývá sada bezplatných generátorů pro S .

Každý volný semigroup (nebo monoid) S má přesně jednu sadu volných generátorů mohutnost z nichž se nazývá hodnost na S .

Dva volné monoidy nebo poloskupiny jsou izomorfní právě tehdy, pokud mají stejnou hodnost. Ve skutečnosti každá sada generátorů pro volnou poloskupinu nebo monoid S obsahuje volné generátory (viz definice generátorů v Monoidu ), protože volný generátor má délku slova 1, a proto jej lze generovat pouze sám. Z toho vyplývá, že volná poloskupina nebo monoid je definitivně generován právě tehdy, pokud má konečnou hodnost.

Submonoid N o A ^* je stabilní , pokud u , v , ux , xv v N společně znamenat x v N . Submonoid A ^∗ je stabilní právě tehdy, je-li zdarma. Například při použití sady bitů {"0", "1"} jako A je sada N všech bitových řetězců obsahujících sudý počet "1" stabilní submonoid, protože pokud u obsahuje sudý počet "1 „s a také ux , pak x musí také obsahovat sudý počet„ 1 “. Zatímco N nelze volně generovat žádnou sadou jednotlivých bitů, lze ji libovolně generovat sadou bitových řetězců {"0", "11", "101", "1001", "10001", ...} - množina řetězců ve tvaru „10 ⁿ 1“ pro celé číslo n .

Kódy

Sada bezplatných generátorů pro volný monoid P se označuje jako základ pro P : sada slov C je kód, pokud C * je volný monoid a C je základ. Sada X slov v A ^∗ je předpona nebo má vlastnost prefix , pokud neobsahuje vlastní (řetězcovou) předponu žádného z jejích prvků. Každá předpona v A ⁺ je kód, ve skutečnosti kód předpony .

Submonoid N o A ^* je přímo jednotný , pokud x , xy v N znamená y v N . Submonoid je generován předponou právě tehdy, je-li správně jednotný.

Faktorizace

Faktorizace volného monoidu je posloupnost podmnožin slov s vlastností, že každé slovo ve volném monoidu lze zapsat jako zřetězení prvků čerpaných z podmnožin. Chen-Fox-Lyndon teorém říká, že Lyndon slova poskytnou faktorizaci. Obecněji řečeno, Hallova slova poskytují faktorizaci; lyndonská slova jsou zvláštním případem Hallových slov.

Volný trup

Průsečík volných submonoidů volného monoidu A ^∗ je opět volný. Pokud je S podmnožinou volného monoidu A *, pak je průsečík všech volných submonoidů A * obsahujících S dobře definovaný, protože A * sám je volný a obsahuje S ; je to zdarma monoid a volal volný trup ze S . Základem této křižovatky je kód.

Tyto vady věta se uvádí, že pokud X je konečný a C je základem volného trupu X , potom buď X je kód a C = X , nebo

| C | ≤ | X | - 1.

Morfismy

Monoid Morfizmus f z volného monoidu B ^* na monoid M je mapa takové, že f ( xy ) = f ( x ) ⋅ f ( y ) pro slov x , y a f (ε) = I, na, kde ε a I, na označuje identity prvek B ^* a M , v tomto pořadí. Morfismus f je určen jeho hodnotami na písmenech B a naopak jakákoli mapa od B po M sahá až k morfismu. Morfismus je nevymazatelný nebo spojitý, pokud není písmeno B mapováno na ι a triviální, pokud je každé písmeno B mapováno na ι.

Morfismus f z volného monoidu B ^∗ na volný monoid A ^∗ je celkový, pokud se každé písmeno A vyskytuje v nějakém slově v obraze f ; cyklický nebo periodický, pokud je obraz f obsažen v { w } ^∗ pro nějaké slovo w z A ^∗ . Morfismus f je k -jednotka, je -li délka | f ( a ) | je konstantní a rovná se k pro všechny A v A . 1-uniformní morfismus je přísně abecední nebo kódovací .

Morfismus f z volného monoidu B ^∗ na volný monoid A ^∗ je zjednodušitelný, pokud existuje abeceda C mohutnosti menší než u B, jako je morfismus f faktorů prostřednictvím C ^∗ , tj. Je to složení morfismu z B ^∗ až C ^∗ a morfismus od toho k A ^∗ ; jinak je f elementární . Morfismus f se nazývá kód, pokud je obrázek abecedy B pod f kódem: každý elementární morfismus je kód.

Testovací sady

Pro L Podskupina B ^* , konečná podmnožina T z L je souprava pro L -li morfizmy f a g na B ^* se shodují v L v případě, a to pouze v případě, že se shodují v T . Ehrenfeucht domněnka je, že jakékoliv z jejích podskupin L má testovací sadu: bylo prokázáno, nezávisle Albert a Lawrence; McNaughton; a Guba. Důkazy se opírají o Hilbertovu teorém .

Mapujte a skládejte

Výpočtovým provedením monoidního morfismu je mapa následovaná záhybem . V tomto nastavení je volný monoid na sadu A odpovídá na seznamu prvků z A s zřetězení jako binární operace. Monomorfní homomorfismus z volného monoidu na jakýkoli jiný monoid ( M , •) je funkce f taková, že

• f ( x ₁ ... x _n ) = f ( x ₁ ) • ... • f ( x _n )
• f () = e

kde e je identity na M . Výpočtově každý takový homomorfismus odpovídá operaci mapy, která aplikuje f na všechny prvky seznamu, následovanou operací skládání, která kombinuje výsledky pomocí binárního operátoru •. Toto výpočetní paradigma (které lze zobecnit na neasociativní binární operátory) inspirovalo softwarový rámec MapReduce .

Endomorfismy

Endomorphism z A ^* je morfismus od A ^* k sobě. Mapa Identita I je endomorphism A ^* a endomorphisms tvoří monoid pod složením funkcí .

Endomorfismus f lze prodloužit, pokud existuje písmeno a takové, že f ( a ) = jako u neprázdného řetězce s .

Řetězcová projekce

Provoz řetězcové projekce je endomorfismus. To znamená, že vzhledem k písmenu a Σ Σ a řetězci s ∈ Σ ^∗ odstraní řetězcová projekce p _a ( s ) každý výskyt a ze s ; je formálně definován

${\ displaystyle p_ {a} (s) = {\ begin {cases} \ varepsilon & {\ text {if}} s = \ varepsilon, {\ text {prázdný řetězec}} \\ p_ {a} (t) & {\ text {if}} s = ta \\ p_ {a} (t) b & {\ text {if}} s = tb {\ text {and}} b \ neq a. \ end {případy}}}$

Všimněte si, že řetězcová projekce je dobře definována, i když je hodnost monoidu nekonečná, protože výše uvedená rekurzivní definice funguje pro všechny řetězce konečné délky. Řetězcová projekce je morfismus v kategorii volných monoidů, takže

${\ displaystyle p_ {a} \ left (\ Sigma ^ {*} \ right) = \ left (\ Sigma -a \ right) ^ {*}}$

kde se rozumí volný monoid všech konečných řetězců, které neobsahují písmeno a . Projekce dojíždí s operací zřetězení řetězců, takže pro všechny řetězce s a t . Existuje mnoho správných inverzí k řetězcové projekci, a jedná se tedy o dělený epimorfismus . ${\ displaystyle p_ {a} \ left (\ Sigma ^ {*} \ right)}$${\ displaystyle p_ {a} (st) = p_ {a} (s) p_ {a} (t)}$

Morfismus identity je definován jako pro všechny řetězce s , a . ${\ displaystyle p _ {\ varepsilon},}$${\ displaystyle p _ {\ varepsilon} (s) = s}$${\ displaystyle p _ {\ varepsilon} (\ varepsilon) = \ varepsilon}$

Řetězcová projekce je komutativní, jak jasně

${\ displaystyle p_ {a} (p_ {b} (s)) = p_ {b} (p_ {a} (s))}}$

U bezplatných monoidů konečné pozice to vyplývá ze skutečnosti, že volné monoidy stejné úrovně jsou izomorfní, protože projekce snižuje pořadí monoidu o jeden.

Řetězcová projekce je idempotentní , jako

${\ displaystyle p_ {a} (p_ {a} (s)) = p_ {a} (s)}$

pro všechny struny s . Projekce je tedy idempotentní, komutativní operace, a tak tvoří ohraničenou semilattice nebo komutativní pásmo .

Zdarma komutativní monoid

Vzhledem k množině A je volný komutativní monoid na A množina všech konečných multisetů s prvky čerpanými z A , přičemž monoidní operace je multisetový součet a monoidní jednotka je prázdná multiset.

Například pokud A = { a , b , c }, prvky volného komutativního monoidu na A jsou ve tvaru

{ε, a , ab , a ² b , ab ³ c ⁴ , ...}.

Základní věta aritmetiky uvádí, že monoid kladných čísel pod násobením je bezplatná komutativní monoid na nekonečné množiny generátorů, na prvočísla .

Volný komutativní pologrupa je podmnožina volného komutativního monoid která obsahuje všechny multimnozin s prvky čerpaných z A kromě prázdné multiset.

Bez částečně komutativní monoid , nebo stopa monoid , je zobecněním, která zahrnuje jak volné a volné komutativní monoidů jako instance. Toto zobecnění nachází uplatnění v kombinatorice a ve studiu paralelismu v informatice .

Viz také

• Řetězcové operace

Poznámky

Reference

• Allouche, Jean-Paul; Shallit, Jeffrey (2003), Automatic Sequences: Theory, Applications, Generalizations , Cambridge University Press , ISBN 978-0-521-82332-6, Zbl  1086,11015
• Berstel, Jean ; Perrin, Dominique ; Reutenauer, Christophe (2010), Codes and automata , Encyclopedia of Mathematics and its Applications, 129 , Cambridge: Cambridge University Press , ISBN 978-0-521-88831-8, Zbl  1187,94001
• Lothaire, M. (1997), Combinatorics on words , Cambridge Mathematical Library, 17 , Přispěvatelé: Perrin, D .; Reutenauer, C .; Berstel, J .; Pin, JE; Pirillo, G .; Foata, D .; Sakarovitch, J .; Simon, I .; Schützenberger, MP; Choffrut, C .; Cori, R. Editoři série: Lyndon, Roger; Rota, Gian-Carlo. Předmluva Rogera Lyndona (2. vyd.), Cambridge University Press , doi : 10.1017 / CBO9780511566097 , ISBN 0-521-59924-5, MR  1475463 , Zbl  0874.20040
• Lothaire, M. (2011), Algebraická kombinatorika slov , Encyklopedie matematiky a její aplikace, 90 , s předmluvou Jean Berstel a Dominique Perrin (Dotisk vázané knihy z roku 2002), Cambridge University Press , ISBN 978-0-521-18071-9, Zbl  1221,68183
• Lothaire, M. (2005), Aplikovaná kombinatorika slov , Encyklopedie matematiky a její aplikace, 105 , Kolektivní dílo Jean Berstel, Dominique Perrin, Maxime Crochemore, Eric Laporte, Mehryar Mohri, Nadia Pisanti, Marie-France Sagot, Gesine Reinert , Sophie Schbath , Michael Waterman, Philippe Jacquet, Wojciech Szpankowski , Dominique Poulalhon, Gilles Schaeffer, Roman Kolpakov, Gregory Koucherov, Jean-Paul Allouche a Valérie Berthé , Cambridge: Cambridge University Press , ISBN 0-521-84802-4, Zbl  1133,68067
• Pytheas Fogg, N. (2002), Berthé, Valérie ; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. (eds.), Substitutions in dynamics, arithmetics and combineatorics , Lecture Notes in Mathematics, 1794 , Berlin: Springer-Verlag , ISBN 3-540-44141-7, Zbl  1014,11015
• Sakarovitch, Jacques (2009), Elements of automata theory , Přeloženo z francouzštiny Reuben Thomas, Cambridge: Cambridge University Press , ISBN 978-0-521-84425-3, Zbl  1188,68177
• Salomaa, Arto (1981), Klenoty teorie formálního jazyka , Pitman Publishing, ISBN 0-273-08522-0, Zbl  0487,68064

externí odkazy

• Média související s Free monoid na Wikimedia Commons