Darmowy monoid - Free monoid

W abstrakcyjnej Algebra The wolne monoid w zestawie jest monoid której wszystkie elementy są na skończone sekwencje (lub łańcuchy) zero lub więcej pierwiastków z tego zbioru, a łączenie łańcucha co monoid pracy i unikalnej sekwencji zerowej elementów, częściej nazywany pustym ciągiem i oznaczany przez ε lub λ, jako element tożsamości . Wolny monoid na zbiorze A jest zwykle oznaczany jako A ^∗ . Darmo półgrupa na A jest sub półgrupa od A ^* zawierający wszystkie elementy z wyjątkiem pusty ciąg. Zwykle jest oznaczony jako A ⁺ .

Bardziej ogólnie, abstrakcyjny monoid (lub półgrupa) S jest opisywany jako wolny, jeśli jest izomorficzny z monoidem swobodnym (lub półgrupą) w pewnym zbiorze.

Jak sama nazwa wskazuje, wolne monoidy i półgrupy to te obiekty, które spełniają zwykłą uniwersalną właściwość definiującą wolne obiekty w odpowiednich kategoriach monoid i półgrup. Wynika z tego, że każdy monoid (lub półgrupa) powstaje jako homomorficzny obraz wolnego monoidu (lub półgrupy). Badanie półgrup jako obrazów wolnych półgrup nazywa się kombinatoryczną teorią półgrup.

Wolne monoidy (i ogólnie monoidy) są z definicji asocjacyjne ; to znaczy, że są zapisywane bez nawiasów, aby pokazać grupowanie lub kolejność operacji. Niezasocjowanym odpowiednikiem jest wolna magma .

Przykłady

Liczby naturalne

Monoid ( N ₀ , +) liczb naturalnych (w tym zero) dodawany jest wolnym monoidem w generatorze wolnym od singletonu, w tym przypadku liczbą naturalną 1. Zgodnie z formalną definicją, monoid ten składa się ze wszystkich ciągów takich jak "1 „,„ 1 + 1 ”,„ 1 + 1 + 1 ”,„ 1 + 1 + 1 + 1 ”itd., Łącznie z pustą sekwencją. Odwzorowanie każdej takiej sekwencji na jej wynik oceny i pusta sekwencja na zero ustala izomorfizm ze zbioru takich sekwencji na N ₀ . Ten izomorfizm jest zgodny z „+”, to znaczy dla dowolnych dwóch sekwencji s i t , jeśli s jest mapowane (tj. Oceniane) na liczbę m i t do n , to ich konkatenacja s + t jest odwzorowywana na sumę m + n .

Gwiazda Kleene

W teorii języka formalnego rozważa się zwykle skończony zbiór „symboli” A (czasami nazywanych alfabetem). Skończony ciąg symboli nazywany jest „słowo na A ”, a wolny monoid ^* jest nazywany „ domknięcie kleene'ego od A ”. Zatem abstrakcyjne badanie języków formalnych można traktować jako badanie podzbiorów nieskończenie generowanych wolnych monoidów.

Na przykład, zakładając alfabet A = { a , b , c }, jego gwiazda Kleene A ^∗ zawiera wszystkie konkatenacje a , b i c :

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

Jeśli A jest jakimkolwiek zbiorem, funkcja długości słowa na A ^∗ jest unikalnym homomorfizmem monoidu od A ^∗ do ( N ₀ , +), który odwzorowuje każdy element z A na 1. Monoid wolny jest więc monoidem stopniowanym . (Monoid stopniowany to monoid, który można zapisać jako . Każdy jest stopniem; ocena to tylko długość ciągu. Oznacza to, że zawiera ciągi długości . Symbol można tutaj traktować jako „sumę zestawu”; jest używany zamiast symbolu, ponieważ generalnie zestawione związki mogą nie być monoidami, dlatego używany jest odrębny symbol. Zgodnie z konwencją gradacje są zawsze zapisywane z 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}$

Istnieją głębokie powiązania między teorią półgrup i teorią automatów . Na przykład każdy język formalny ma monoid składniowy, który rozpoznaje ten język. W przypadku języka regularnego monoid ten jest izomorficzny z monoidem przejściowym związanym z półautomatonem jakiegoś deterministycznego automatu skończonego, który rozpoznaje ten język. Języki regularne nad alfabetem A są zamknięciem skończonych podzbiorów A *, wolnej monoidy nad A, pod zjednoczeniem, iloczynem i generacją submonoida.

W przypadku obliczeń współbieżnych , to znaczy systemów z blokadami , muteksami lub łączeniami wątków , obliczenia można opisać za pomocą monoidów historii i monoidów śledzenia . Z grubsza mówiąc, elementy monoidu mogą komutować (np. Różne wątki mogą być wykonywane w dowolnej kolejności), ale tylko do blokady lub muteksu, co zapobiega dalszej komutacji (np. Serializuje dostęp wątku do jakiegoś obiektu).

Sprzężone słowa

Przykład pierwszego przypadku równoważności: m = „UNCLE”, n = „ANLY”, p = „UN”, q = „CLEANLY” i s = „CLE”

Definiujemy parę słów w A ^∗ w postaci uv i vu jako koniugat : koniugaty słowa są więc jego przesunięciami okrężnymi . Dwa słowa są sprzężone w tym sensie, jeżeli są one sprzężone w sensie teorii grup jako elementów wolnej grupy generowanego przez A .

Eliminowalność

Wolny monoid jest równoważny : jeśli zachodzi równanie mn = pq , to istnieje s takie, że albo m = ps , sn = q (przykład patrz rysunek), albo ms = p , n = sq . Ten wynik jest również znany jako lemat Leviego .

Monoid jest bezpłatny wtedy i tylko wtedy, gdy jest stopniowany i równoważny.

Darmowe generatory i ranga

Członkowie zbioru A nazywani są wolnymi generatorami dla A ^∗ i A ⁺ . Indeks górny * jest wtedy powszechnie rozumiany jako gwiazda Kleene . Mówiąc bardziej ogólnie, jeśli S jest abstrakcyjnym monoidem swobodnym (półgrupą), to zbiór elementów, które są mapowane na zbiór jednoliterowych słów pod izomorfizmem do półgrupy A ⁺ (monoid A ^∗ ) nazywany jest zestawem wolnych generatorów dla S .

Każdy wolny półgrupa (lub monoid) S ma dokładnie jeden zestaw darmowych generatorów The liczności , których nazywa się ranga od S .

Dwie wolne monoidy lub półgrupy są izomorficzne wtedy i tylko wtedy, gdy mają tę samą rangę. W rzeczywistości każdy zestaw generatorów dla dowolnej półgrupy lub monoidu S zawiera wolne generatory (patrz definicja generatorów w Monoid ), ponieważ wolny generator ma długość słowa 1, a zatem może być generowany tylko sam. Wynika z tego, że wolna półgrupa lub monoida jest generowana w sposób skończony wtedy i tylko wtedy, gdy ma skończoną rangę.

Submonoid N o A ^* jest stabilny , jeśli u , v , zwrotną , xv w N razem oznaczać X w N . Podmonoid A ^∗ jest stabilny wtedy i tylko wtedy, gdy jest wolny. Na przykład, używając zestawu bitów {"0", "1"} jako A , zbiór N wszystkich ciągów bitów zawierających parzystą liczbę „1” jest stabilnym submonoidem, ponieważ jeśli u zawiera parzystą liczbę „1” "s i ux również, wtedy x musi zawierać parzystą liczbę" 1 ". Chociaż N nie może być dowolnie generowane przez żaden zestaw pojedynczych bitów, może być dowolnie generowane przez zestaw ciągów bitów {"0", "11", "101", "1001", "10001", ...} - zbiór ciągów postaci „10 ⁿ 1” dla pewnej liczby całkowitej n .

Kody

Zbiór wolnych generatorów dla wolnego monoidu P jest określany jako podstawa dla P : zbiór słów C jest kodem, jeśli C * jest wolnym monoidem, a C jest podstawą. Zbiór X słów w A ^∗ jest przedrostkiem lub ma właściwość prefiksu , jeśli nie zawiera właściwego (łańcuchowego) przedrostka żadnego z jego elementów. Każdy prefiks w A ⁺ jest kodem, a właściwie kodem prefiksu .

Submonoid N o A ^* jest tuż jednolity , gdy x , xy w N oznacza Y w N . Podmonoid jest generowany przez przedrostek wtedy i tylko wtedy, gdy jest poprawnie unitarny.

Faktoryzacja

Rozłożenie na czynniki monoidu swobodnego to sekwencja podzbiorów słów z właściwością, że każde słowo w monoidzie swobodnym może być zapisane jako konkatenacja elementów pobranych z podzbiorów. Twierdzenie Chen – Fox – Lyndon stwierdza, że słowa Lyndona zapewniają faktoryzację. Bardziej ogólnie, słowa Hall zapewniają faktoryzację; słowa Lyndona są szczególnym przypadkiem słów Hall.

Wolny kadłub

Przecięcie wolnych submonoidów wolnego monoidu A ^∗ jest znowu wolne. Jeśli S jest podzbiorem swobodnego monoidu A *, to przecięcie wszystkich wolnych podmonoidów A * zawierających S jest dobrze zdefiniowane, ponieważ samo A * jest wolne i zawiera S ; jest wolny monoid i zwany wolny kadłub z S . Podstawą tego skrzyżowania jest kod.

W twierdzenie wadę , że jeśli X jest skończona i C jest zasadach kadłuba X , wówczas X jest w kod i C = X , lub

| C | ≤ | X | - 1.

Morfizmy

Monoid morfizmem F z wolnego monoid B ^* do monoid M jest mapą, tak że F ( XY ) = f ( x ) ⋅ F ( y ) słowa x , y i f (ε) = ι, gdzie ε i ι oznacza element identyfikacyjny B ^* i M odpowiednio. Morfizm f jest określony przez jego wartości w literach B i odwrotnie, każda mapa od B do M rozciąga się na morfizm. Morfizm jest nieusuwalny lub ciągły, jeśli żadna litera B nie jest odwzorowany na ι, i trywialny, jeśli każda litera B jest odwzorowywana na ι.

Morfizm f z wolnego monoidu B ^∗ do wolnego monoidu A ^∗ jest całkowity, jeśli każda litera A występuje w jakimś słowie na obrazie f ; cykliczne lub okresowe, jeśli obraz f jest zawarty w { w } ^∗ dla jakiegoś słowa w z A ^∗ . Morfizm f jest k -jednorodny, jeśli długość | f ( a ) | jest stała i równa k dla wszystkich A w A . Jednolity morfizm 1 jest ściśle alfabetyczny lub kodowany .

Morfizm f z monoidu wolnego B ^∗ do monoidu swobodnego A ^∗ można uprościć, jeśli istnieje alfabet C o liczności mniejszej niż alfabet B, taki jak czynniki morfizmu f do C ^∗ , to znaczy jest to skład morfizmu z B ^∗ do C ^∗ i morfizm od tego do A ^∗ ; w przeciwnym razie f jest elementarne . Morfizm f nazywany jest kodem, jeśli obraz alfabetu B pod f jest kodem: każdy elementarny morfizm jest kodem.

Zestawy testowe

Dla L podzbiór B ^* , skończoną podzbioru T z L jest zestaw testowy dla L , jeśli morfizmami F i G w B ^* się z L , wtedy i tylko wtedy, gdy się z T . Ehrenfeucht przypuszczenie , że dowolny zestaw L zawiera zestaw testowy: wykazano niezależnie Albert Lawrence; McNaughton; i Guba. Dowody opierają się na twierdzeniu Hilberta o podstawie .

Mapuj i złóż

Obliczeniowym ucieleśnieniem morfizmu monoidalnego jest mapa, po której następuje zagięcie . W tym ustawieniu, wolny monoid w zbiorze A odpowiada listom elementów z A z konkatenacją jako operacją binarną. Homomorfizm monoidu z wolnego monoidu do dowolnego innego monoidu ( M , •) jest funkcją f taką, że

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

gdzie e jest tożsamość na M . Z punktu widzenia obliczeń, każdy taki homomorfizm odpowiada operacji na mapie stosującej f do wszystkich elementów listy, po której następuje operacja zwinięcia , która łączy wyniki za pomocą operatora binarnego •. Ten paradygmat obliczeniowy (który można uogólnić na nieasocjacyjne operatory binarne) zainspirował strukturę oprogramowania MapReduce .

Endomorfizmy

Endomorfizm od A ^* jest morfizmem od A ^* do siebie. Mapa tożsamość ja to endomorfizm od A ^* , a endomorfizm tworzą monoid pod składu funkcji .

Endomorfizm f jest przedłużalny, jeśli istnieje taka litera a , że f ( a ) = jak dla niepustego łańcucha s .

Projekcja strun

Operacja projekcji strun jest endomorfizmem. To znaczy, biorąc pod uwagę literę a ∈ Σ i łańcuch s ∈ Σ ^∗ , projekcja napisu p _a ( s ) usuwa każde wystąpienie a z s ; jest formalnie zdefiniowany przez

${\ Displaystyle p_ {a} (s) = {\ rozpocząć {przypadki} \ varepsilon & {\ tekst {if}} s = \ varepsilon, {\ tekst {pusty ciąg}} \\ p_ {a} (t) & {\ text {if}} s = ta \\ p_ {a} (t) b & {\ text {if}} s = tb {\ text {i}} b \ neq a. \ end {przypadki}}}$

Zwróć uwagę, że rzutowanie na ciąg jest dobrze zdefiniowane, nawet jeśli rząd monoidu jest nieskończony, ponieważ powyższa definicja rekurencyjna działa dla wszystkich ciągów o skończonej długości. Projekcja strun jest więc morfizmem w kategorii monoidów swobodnych

${\ Displaystyle p_ {a} \ lewo (\ Sigma ^ {*} \ prawej) = \ lewo (\ Sigma -a \ prawo) ^ {*}}$

gdzie jest rozumiany jako wolny monoid wszystkich skończonych ciągów, które nie zawierają litery a . Projekcja zamienia się z operacją konkatenacji ciągów, tak że dla wszystkich ciągów s i t . Istnieje wiele prawoskrętnych odwrotności do projekcji strun, a zatem jest to podzielony epimorfizm . ${\ Displaystyle p_ {a} \ lewo (\ Sigma ^ {*} \ prawej)}$${\ displaystyle p_ {a} (st) = p_ {a} (s) p_ {a} (t)}$

Morfizm tożsamości jest definiowany jak dla wszystkich ciągów s , i . ${\ displaystyle p _ {\ varepsilon},}$${\ Displaystyle p _ {\ varepsilon} (s) = s}$${\ Displaystyle p _ {\ varepsilon} (\ varepsilon) = \ varepsilon}$

Projekcja strun jest przemienna, jak widać

${\ Displaystyle p_ {a} (p_ {b} (s)) = p_ {b} (p_ {a} (s)).}$

W przypadku wolnych monoidów o skończonej randze wynika to z faktu, że wolne monoidy o tej samej randze są izomorficzne, ponieważ rzutowanie zmniejsza rangę monoidu o jeden.

Projekcja ciągu jest idempotentna , tak jak

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

na wszystkie struny s . Zatem projekcja jest idempotentną, przemienną operacją, a więc tworzy ograniczony półksiężyc lub pasmo przemienne .

Wolny monoid przemienny

Biorąc pod uwagę zbiór A , wolny monoid przemienny na A jest zbiorem wszystkich skończonych multizbiorów z elementami pobranymi z A , przy czym operacja monoidalna jest sumą wielozbiorową, a jednostka monoidalna jest pustym zestawem wielokrotnym.

Na przykład, jeśli A = { a , b , c }, elementy wolnego monoidu przemiennego na A mają postać

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

Podstawowe twierdzenie arytmetyki stanach że monoid liczb całkowitych dodatnich pod mnożenia to darmowa przemienne monoid na nieskończony zbiór generatorów, z liczb .

Wolne przemienne półgrupa jest podzbiorem wolnej monoid przemiennego, który zawiera wszystkie elementy multisets z zaczerpniętych z A, oprócz pustych MultiSet.

Wolne częściowo przemienne monoid lub ślad monoid jest uogólnieniem, że obejmuje zarówno wolną i wolne przemienne monoids jak przypadkach. To uogólnienie znajduje zastosowanie w kombinatoryce i badaniach równoległości w informatyce .

Zobacz też

• Operacje na łańcuchach

Uwagi

Bibliografia

• 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 , współpracownicy: Perrin, D .; Reutenauer, C .; Berstel, J .; Pin, JE; Pirillo, G .; Foata, D .; Sakarovitch, J .; Simon, I .; Poseł Schützenberger; Choffrut, C .; Cori, R. Redaktorzy serii: Lyndon, Roger; Rota, Gian-Carlo. Przedmowa Rogera Lyndona (wyd. 2), Cambridge University Press , doi : 10.1017 / CBO9780511566097 , ISBN 0-521-59924-5, MR  1475463 , Zbl  0874.20040
• Lothaire, M. (2011), Algebraic combinatorics on words , Encyclopedia of Mathematics and Its Applications, 90 , z przedmową Jean Berstel i Dominique Perrin (Reprint of the 2002 hardback ed.), Cambridge University Press , ISBN 978-0-521-18071-9, Zbl  1221.68183
• Lothaire, M. (2005), Applied combinatorics on words , Encyclopedia of Mathematics and Its Applications, 105 , A zbiorowa praca 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 and 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. (red.), Substitutions in dynamics, arytmetics and combinatorics , Lecture Notes in Mathematics, 1794 , Berlin: Springer-Verlag , ISBN 3-540-44141-7, Zbl  1014.11015
• Sakarovitch, Jacques (2009), Elementy teorii automatów , przekład z języka francuskiego Reuben Thomas, Cambridge: Cambridge University Press , ISBN 978-0-521-84425-3, Zbl  1188.68177
• Salomaa, Arto (1981), Jewels of Formal Language Theory , Pitman Publishing, ISBN 0-273-08522-0, Zbl  0487.68064

Linki zewnętrzne

• Multimedia związane z Free monoid w Wikimedia Commons