Automatisk semigrupp

Inom matematik är en automatisk halvgrupp en finitely genererad halvgrupp utrustad med flera vanliga språk över ett alfabet som representerar en genereringsmängd. Ett av dessa språk bestämmer "kanoniska former" för elementen i halvgruppen, de andra språken avgör om två kanoniska former representerar element som skiljer sig åt genom multiplikation med en generator.

Formellt, låt $S$ vara en halvgrupp och $A$ vara en ändlig uppsättning generatorer. Sedan består en automatisk struktur för $S$ med avseende på $A$ av ett reguljärt språk $L$ över $A$ så att varje element i $S$ har minst en representant i $L$ och sådan att för varje $a\in A\cup \{\varepsilon \}$ , relationen som består av par $(u,v)$ med $ua=v$ är regelbunden, ses som en delmängd av ( A ^# × A ^# )*. Här är A ^# A förstärkt med en utfyllnadssymbol.

Konceptet med en automatisk semigrupp generaliserades från automatiska grupper av Campbell et al. (2001)

Till skillnad från automatiska grupper (se Epstein et al. 1992) kan en semigrupp ha en automatisk struktur med avseende på en genereringsmängd, men inte med avseende på en annan. Men om en automatisk halvgrupp har en identitet, så har den en automatisk struktur med avseende på vilken generering som helst (Duncan et al. 1999).

Beslutsproblem

Liksom automatiska grupper har automatiska semigrupper ordproblem som kan lösas i kvadratisk tid. Kambites & Otto (2006) visade att det är oavgörbart om ett element i en automatisk monoid har en rätt invers.

Cain (2006) bevisade att både cancellativity och left-cancellativity är obestämbara för automatiska semigrupper. Å andra sidan är högercancellativitet avgörbar för automatiska semigrupper (Silva & Steinberg 2004).

Geometrisk karaktärisering

Automatiska strukturer för grupper har en elegant geometrisk karaktärisering som kallas medresenärsegenskapen (Epstein et al. 1992, kap. 2). Automatiska strukturer för semigrupper besitter medresenärens egendom men karaktäriseras inte generellt av den (Campbell et al. 2001). Karakteriseringen kan dock generaliseras till vissa " gruppliknande " klasser av semigrupper, särskilt helt enkla semigrupper (Campbell et al. 2002) och gruppinbäddningsbara semigrupper (Cain et al. 2006).

Exempel på automatiska semigrupper

• Bicyklisk monoid
• Fint genererade underhalvgrupper av en fri halvgrupp

•   Cain, Alan J. (2006), "Cancellativity is undecidable for automatic semigroups", Quarterly Journal of Mathematics , 57 (3): 285–295, CiteSeerX 10.1.1.106.6068 , doi : 10.1093/23math
• Cain, Alan J.; Robertson, Edmund F.; Ruskuc, Nik (2006), "Subsemigroups of groups: presentations, Malcev presentations, and automatic structures", 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), "Automatic quite simple semigroups", Acta Mathematica Hungarica , 95 (3): 201–215, doi : 10.1023/A:1015632704977 .
• Duncan, AJ; Robertson, EF; Ruskuc, N. (1999), "Automatic monoids and change of generators", Mathematical Proceedings of the Cambridge Philosophical Society , 127 (3): 403–409, doi : 10.1017/S0305004199003722 .
•   Epstein, David BA ; Cannon, James W. ; Holt, Derek F.; Levy, Silvio VF; Paterson, Michael S. ; Thurston, William P. (1992), Word Processing in Groups , Boston, MA: Jones and Bartlett Publishers, ISBN 0-86720-244-0 .
• Kambites, Mark; Otto, F (2006), "Uniform decision problems for automatic semigroups", Journal of Algebra , 303 (2): 789–809, arXiv : math/0509349 , doi : 10.1016/j.jalgebra.2005.11.028
•   Silva, PV; Steinberg, B. (2004), "A geometric characterization of automatic monoids", Quarterly Journal of Mathematics , 55 (3): 333–356, CiteSeerX 10.1.1.36.1681 , doi : 10.1093/qmath/hah006

Vidare läsning

•   Hoffmann, Michael; Kuske, Dietrich; Otto, Friedrich; Thomas, Richard M. (2002), "Some relatives of automatic and hyperbolic groups", i Gomes, Gracinda MS (red.), Semigroups, algorithms, automata and languages. Proceedings of workshops hölls vid International Centre of Mathematics, CIM, Coimbra, Portugal, maj, juni och juli 2001, Singapore: World Scientific, s. 379–406, Zbl 1031.20047