Transformační poloskupina - Transformation semigroup

v algebra, a transformační poloskupina (nebo složení poloskupina) je sbírka funkce ze sady pro sebe to je Zavřeno pod složení funkce. Pokud obsahuje funkce identity, to je monoidní, nazvaný a proměna (nebo složení) monoidní. To je poloskupina analogie a permutační skupina.

Transformační poloskupina sady má tautologii akce poloskupiny na tom setu. Takové akce se vyznačují tím, že jsou účinné, tj. Mají-li dva prvky poloskupiny stejnou akci, jsou stejné.

Analog z Cayleyho věta ukazuje, že kteroukoli poloskupinu lze realizovat jako transformační poloskupinu nějaké sady.

v teorie automatů, někteří autoři tento termín používají transformační poloskupina odkazovat na poloskupinu jedná věrně na množině „stavů“ odlišných od základní množiny poloskupiny.^[1] Tady je korespondence mezi těmito dvěma pojmy.

Transformační poloskupiny a monoidy

A transformační poloskupina je pár (X,S), kde X je sada a S je poloskupina transformací X. Tady a proměna z X je jen a částečná funkce z podskupiny X na X, nemusí být nutně invertibilní, a proto S je prostě sada transformací X který je Zavřeno pod složení funkcí. Sada všech dílčích funkcí na dané základní sadě, X, tvoří a pravidelná poloskupina nazývá se poloskupina všech částečných transformací (nebo semigroup částečné transformace na X), obvykle označován ${displaystyle {mathcal {PT}} _ {X}}$ .^[2]

Li S zahrnuje transformaci identity X, pak se nazývá a transformační monoid. Je zřejmé, že každá transformační poloskupina S určuje transformační monoid M převzetím unie S s transformací identity. Transformační monoid, jehož prvky jsou invertibilní, je a permutační skupina.

Sada všech transformací X je transformační monoid zvaný plný transformační monoid (nebo poloskupina) z X. Také se tomu říká symetrická poloskupina z X a je označen T_X. Transformační poloskupina (nebo monoid) je tedy jen a podskupina (nebo submonoid ) úplného transformačního monoidu o X.

Pokud (X,S) je tedy transformační poloskupina X lze udělat z akce poloskupiny z S podle hodnocení:

{displaystyle scdot x = s (x) {ext {for}} sin S, xin X.}

Jde o monoidní akci, pokud S je transformační monoid.

Charakteristickým rysem transformačních poloskupin, jako akcí, je to, že jsou efektivní, tj. pokud

{displaystyle scdot x = tcdot x {ext {pro všechny}} xin X,}

pak s = t. Naopak, pokud poloskupina S působí na množinu X podle T(s,X) = s • X pak můžeme definovat, protože s ∈ S, transformace T_s z X podle

{displaystyle T_ {s} (x) = T (s, x).,}

Odesílání mapy s na T_s je injekční právě tehdy, když (X, T) je efektivní, v takovém případě je obraz této mapy transformační poloskupinou isomorfní na S.

Cayley zastoupení

v teorie skupin, Cayleyho věta tvrdí, že každá skupina G je izomorfní s podskupinou symetrická skupina z G (považováno za sadu), takže G je permutační skupina. Tato věta se zobecňuje přímo na monoidy: jakýkoli monoid M je transformační monoid své základní množiny prostřednictvím akce dané levým (nebo pravým) násobením. Tato akce je účinná, protože pokud sekera = bx pro všechny X v M, pak tím, že X rovná se prvku identity, máme A = b.

Pro poloskupinu S bez (levého nebo pravého) prvku identity vezmeme X být podkladovou sadou monoid odpovídající S uvědomit si S jako transformační poloskupina X. Zejména jakoukoli konečnou poloskupinu lze reprezentovat jako a podskupina transformací množiny X s |X| ≤ |S| + 1, a pokud S je monoid, máme ostřejší vazbu |X| ≤ |S|, jako v případě konečné skupiny.^[3]^:21

V počítačové vědě

v počítačová věda „Cayleyho reprezentace lze použít ke zlepšení asymptotické účinnosti semigroup opětovným přidružením několika složených multiplikací. Akce daná multiplikací vlevo má za následek multiplikaci spojenou s právem a naopak pro akci danou multiplikací vpravo. I přes stejné výsledky pro jakoukoli poloskupinu se bude asymptotická účinnost lišit. Dva příklady užitečných transformačních monoidů daných působením levého násobení jsou funkční variace seznam rozdílů datová struktura a monadická transformace Codensity (Cayleyova reprezentace a monad, což je konkrétně monoid monoidální kategorie funktorů ).^[4]

Transformační monoid automatu

Nechat M být deterministický automat se stavovým prostorem S a abeceda A. Slova v volný monoid A^∗ vyvolat transformace S což vede k a monoidní morfismus z A^∗ na monoid plné transformace T_S. Obrazem tohoto morfismu je transformační poloskupina M.^[3]^:78

Pro běžný jazyk, syntaktický monoid je izomorfní s transformačním monoidem minimální automat jazyka.^[3]^:81

Viz také

Reference

^ Dominique Perrin; Jean Eric Pin (2004). Nekonečná slova: automaty, poloskupiny, logika a hry. Akademický tisk. p. 448. ISBN 978-0-12-532111-2.
^ Alfred Hoblitzelle Clifford; G. B. Preston (1967). Algebraická teorie poloskupin. Svazek II. American Mathematical Soc. p. 254. ISBN 978-0-8218-0272-4.
^ ^A ^b ^C Anderson, James A. (2006). Teorie automatů s moderními aplikacemi. S příspěvky Toma Heada. Cambridge: Cambridge University Press. doi:10.1017 / CBO9780511607202. ISBN 978-0-521-61324-8. Zbl 1127.68049.
^ Rivas, Exequiel; Jaskelioff, Mauro (2017). "Pojmy výpočtu jako monoidy". Journal of Functional Programming. 27 (e21). arXiv:1406.4823. doi:10.1017 / S0956796817000132.

Clifford, A.H .; Preston, GB (1961). Algebraická teorie poloskupin. Sv. Já. Matematické průzkumy. 7. Providence, R.I .: Americká matematická společnost. ISBN 978-0-8218-0272-4. Zbl 0111.03403.
Howie, John M. (1995). Základy teorie semigroup. Monografie London Mathematical Society. Nová řada. 12. Oxford: Clarendon Press. ISBN 978-0-19-851194-6. Zbl 0835.20077.
Mati Kilp, Ulrich Knauer, Alexander V. Mikhalev (2000), Monoidy, akty a kategorie: s aplikacemi na produkty a grafy věnců„Expozice v matematice 29, Walter de Gruyter, Berlín, ISBN 978-3-11-015248-7.

[PerrinPin2004-1] Dominique Perrin; Jean Eric Pin (2004). Nekonečná slova: automaty, poloskupiny, logika a hry. Akademický tisk. p. 448. ISBN 978-0-12-532111-2.

[CliffordPreston1967-2] Alfred Hoblitzelle Clifford; G. B. Preston (1967). Algebraická teorie poloskupin. Svazek II. American Mathematical Soc. p. 254. ISBN 978-0-8218-0272-4.

[JAA-3] A ^b ^C Anderson, James A. (2006). Teorie automatů s moderními aplikacemi. S příspěvky Toma Heada. Cambridge: Cambridge University Press. doi:10.1017 / CBO9780511607202. ISBN 978-0-521-61324-8. Zbl 1127.68049.

[4] Rivas, Exequiel; Jaskelioff, Mauro (2017). "Pojmy výpočtu jako monoidy". Journal of Functional Programming. 27 (e21). arXiv:1406.4823. doi:10.1017 / S0956796817000132.

[1]

[2]

[3]

[4]