Automatyczna półgrupa

W matematyce automatyczna półgrupa to skończenie generowana półgrupa wyposażona w kilka języków regularnych nad alfabetem reprezentującym zespół generujący. Jeden z tych języków określa „formy kanoniczne” dla elementów półgrupy, inne języki określają, czy dwie formy kanoniczne reprezentują elementy, które różnią się przez pomnożenie przez generator.

Formalnie niech $półgrupą$ i $skończonym$ zbiorem generatorów Następnie automatyczna struktura dla w odniesieniu do składa się z $S$ regularnego nad takim, że każdy element ${$${\ displaystyle S$$displaystyle$$S$ ma co najmniej jeden przedstawiciel w $taki$ , że dla każdego relacji składającej się z par ${\ Displaystyle (u, v)}$$}}$ gdzie ${\ displaystyle ua = v}$ jest regularne, postrzegane jako podzbiór ( ZA ^# × A ^# ) *. Tutaj A ^# to A powiększone o symbol dopełnienia.

Koncepcja automatycznej półgrupy została uogólniona z grup automatycznych przez Campbella i in. (2001)

W przeciwieństwie do grup automatycznych (zob. Epstein i in. 1992), półgrupa może mieć strukturę automatyczną w odniesieniu do jednego zespołu prądotwórczego, ale nie w odniesieniu do innego. Jeśli jednak automatyczna półgrupa ma tożsamość, to ma automatyczną strukturę w odniesieniu do dowolnego zespołu generującego (Duncan i in. 1999).

Problemy decyzyjne

Podobnie jak grupy automatyczne, automatyczne półgrupy mają zadanie tekstowe , które można rozwiązać w czasie kwadratowym. Kambites i Otto (2006) wykazali, że nie można rozstrzygnąć, czy element automatycznego monoidu ma prawą odwrotność.

Cain (2006) udowodnił, że zarówno anulacyjność, jak i lewostronna anulacyjność są nierozstrzygalne dla półgrup automatycznych. Z drugiej strony prawostronność jest rozstrzygalna dla półgrup automatycznych (Silva i Steinberg 2004).

Charakterystyka geometryczna

Automatyczne struktury dla grup mają elegancką charakterystykę geometryczną zwaną właściwością towarzysza podróży (Epstein i in. 1992, rozdz. 2). Automatyczne struktury dla półgrup posiadają właściwość towarzysza podróży, ale generalnie nie są nią charakteryzowane (Campbell et al. 2001). Jednak charakterystykę można uogólnić na pewne „ grupopodobne ” klasy półgrup, zwłaszcza całkowicie proste półgrupy (Campbell i in. 2002) oraz półgrupy możliwe do osadzenia w grupach (Cain i in. 2006).

Przykłady półgrup automatycznych

• Monoid bicykliczny
• Skończenie wygenerowane podgrupy swobodnej półgrupy

•   Cain, Alan J. (2006), „Anulowanie jest nierozstrzygalne dla automatycznych półgrup” , Quarterly Journal of Mathematics , 57 (3): 285–295, CiteSeerX 10.1.1.106.6068 , doi : 10.1093/qmath/hai023
• Kain, Alan J.; Robertson, Edmund F.; Ruskuc, Nik (2006), „Podgrupy grup: prezentacje, prezentacje Malceva i struktury automatyczne”, Journal of Group Theory , 9 (3): 397–426, doi : 10.1515 / JGT.2006.027 .
• Campbell, Colin M.; Robertson, Edmund F.; Ruskuc, Nik; Thomas, Richard M. (2002), „Automatyczne całkowicie proste półgrupy” , Acta Mathematica Hungarica , 95 (3): 201–215, doi : 10,1023 / A: 1015632704977 .
• Duncan, AJ; Robertson, EF; Ruskuc, N. (1999), „Automatyczne monoidy i zmiana generatorów”, Mathematical Proceedings of the Cambridge Philosophical Society , 127 (3): 403–409, doi : 10.1017 / S0305004199003722 .
•   Epstein, David BA ; Działo, James W .; Holt, Derek F.; Levy, Silvio VF; Paterson, Michael S .; Thurston, William P. (1992), Przetwarzanie tekstu w grupach , Boston, MA: Jones and Bartlett Publishers, ISBN 0-86720-244-0 .
• Kambites, Marek; Otto, F (2006), „Jednolite problemy decyzyjne dla automatycznych półgrup”, Journal of Algebra , 303 (2): 789–809, arXiv : math / 0509349 , doi : 10.1016/j.jalgebra.2005.11.028
•   Silva, PV; Steinberg, B. (2004), „Geometryczna charakterystyka monoidów automatycznych” , Quarterly Journal of Mathematics , 55 (3): 333–356, CiteSeerX 10.1.1.36.1681 , doi : 10.1093/qmath/hah006

Dalsza lektura

•   Hoffmann, Michael; Kuske, Dietrich; Otto, Friedrich; Thomas, Richard M. (2002), „Niektórzy krewni grup automatycznych i hiperbolicznych”, w Gomes, Gracinda MS (red.), Półgrupy, algorytmy, automaty i języki. Materiały z warsztatów przeprowadzonych w Międzynarodowym Centrum Matematyki, CIM, Coimbra, Portugalia, maj, czerwiec i lipiec 2001 , Singapur: World Scientific, s. 379–406, Zbl 1031.20047