Automatická poloskupina - Automatic semigroup - Wikipedia

v matematika, an automatická poloskupina je definitivně generován poloskupina vybaveno několika běžné jazyky přes abecedu představující generující množinu. Jeden z těchto jazyků určuje „kanonické formy“ pro prvky poloskupiny, ostatní jazyky určují, zda dvě kanonické formy představují prvky, které se liší vynásobením generátorem.

Formálně, pojďme ${ displaystyle S}$ být poloskupinou a ${ displaystyle A}$ být konečnou sadou generátorů. Pak automatická struktura pro ${ displaystyle S}$ s ohledem na ${ displaystyle A}$ skládá se z běžného jazyka ${ displaystyle L}$ přes ${ displaystyle A}$ tak, že každý prvek ${ displaystyle S}$ má alespoň jednoho zástupce v ${ displaystyle L}$ a takové, že pro každého ${ displaystyle a v A cup { varepsilon }}$ , vztah skládající se z párů ${ displaystyle (u, v)}$ s ${ displaystyle ua = v}$ je normální, je považováno za podmnožinu (A^# × A^#) *. Tady A^# je A doplněno vycpávkovým symbolem.^[1]

Koncept automatické poloskupiny byl zobecněn z automatické skupiny Campbell et al. (2001)

Na rozdíl od automatických skupin (viz Epstein et al. 1992) může mít poloskupina automatickou strukturu s ohledem na jednu generující množinu, ale ne s ohledem na druhou. Pokud však automatická semigroup má identitu, pak má automatickou strukturu s ohledem na jakoukoli generující sadu (Duncan et al. 1999).

Problémy s rozhodováním

Stejně jako automatické skupiny mají i automatické poloskupiny slovní úloha řešitelný v kvadratickém čase. Kambites & Otto (2006) ukázali, že je nerozhodné, zda prvek automatického monoidu má správnou inverzi.

Cain (2006) prokázal, že u automatických semigrafů nelze zrušit ani zrušit, ani zrušit. Na druhou stranu je pravá storlativnost rozhodnutelná pro automatické poloskupiny (Silva & Steinberg 2004).

Geometrická charakterizace

Automatické struktury pro skupiny mají elegantní geometrickou charakterizaci zvanou majetek spolucestujících (Epstein a kol. 1992, kap. 2). Automatické struktury pro poloskupiny mít majetek spolucestujících, ale není jím obecně charakterizován (Campbell et al. 2001). Charakterizaci však lze zobecnit na určité „skupina „třídy“ poloskupin, zejména zcela jednoduché poloskupiny (Campbell et al. 2002) a skupinově zabudovatelné semigroup (Cain et al. 2006).

Příklady automatických poloskupin

Bicyklický monoid
Konečně generované podskupiny a bezplatná poloskupina

Reference

^ Campbell, Colin M .; Robertson, Edmund F .; Ruskoc, Nik; Thomas, Richard M. (2001), "Automatické poloskupiny" (PDF), Teoretická informatika, 250 (1–2): 365–391, doi:10.1016 / S0304-3975 (99) 00151-6.

Cain, Alan J. (2006), „Cancellativita je pro automatické semigroup nerozhodnutelná“, Quarterly Journal of Mathematics, 57 (3): 285–295, CiteSeerX 10.1.1.106.6068, doi:10.1093 / qmath / hai023
Cain, Alan J .; Robertson, Edmund F .; Ruskoc, Nik (2006), „Podskupiny skupin: prezentace, prezentace Malcev a automatické struktury“, Journal of Group Theory, 9 (3): 397–426, doi:10.1515 / JGT.2006.027.
Campbell, Colin M .; Robertson, Edmund F .; Ruskoc, Nik; Thomas, Richard M. (2002), „Automatické zcela jednoduché poloskupiny“, Acta Mathematica Hungarica, 95 (3): 201–215, doi:10.1023 / A: 1015632704977.
Duncan, A. J .; Robertson, E. F .; Ruskoc, N. (1999), „Automatické monoidy a výměna generátorů“, Mathematical Proceedings of the Cambridge Philosophical Society, 127 (3): 403–409, doi:10.1017 / S0305004199003722.
Epstein, David B. A.; Dělo, James W.; Holt, Derek F .; Levy, Silvio V. F .; Paterson, Michael S.; Thurston, William P. (1992), Zpracování textu ve skupinách, Boston, MA: vydavatelé Jones a Bartlett, ISBN 0-86720-244-0.
Kambites, Mark; Otto, F (2006), „Problémy s jednotným rozhodováním pro automatické poloskupiny“, Journal of Algebra, 303 (2): 789–809, arXiv:matematika / 0509349, doi:10.1016 / j.jalgebra.2005.11.028
Silva, P.V .; Steinberg, B. (2004), „Geometrická charakterizace automatických monoidů“, Quarterly Journal of Mathematics, 55 (3): 333–356, CiteSeerX 10.1.1.36.1681, doi:10.1093 / qmath / hah006

Další čtení

Hoffmann, Michael; Kuske, Dietrich; Otto, Friedrich; Thomas, Richard M. (2002), „Někteří příbuzní automatických a hyperbolických skupin“, Gomes, Gracinda M. S. (ed.), Poloskupiny, algoritmy, automaty a jazyky. Sborník workshopů konaných v Mezinárodním středisku matematiky, CIM, Coimbra, Portugalsko, květen, červen a červenec 2001, Singapur: World Scientific, s. 379–406, Zbl 1031.20047

[1] Campbell, Colin M .; Robertson, Edmund F .; Ruskoc, Nik; Thomas, Richard M. (2001), "Automatické poloskupiny" (PDF), Teoretická informatika, 250 (1–2): 365–391, doi:10.1016 / S0304-3975 (99) 00151-6.

[1]