ON AUTOMATIC REES MATRIX SEMIGROUPS

ONAUTOMATICREESMATRIXSEMIGROUPSL.DesaloandN.RuskuMathematialInstitute,UniversityofStAndrewsStAndrewsKY169SS,SotlandAbstratWeonsideraReesmatrixsemigroupS=M[U;I;J;P℄overasemigroupU,withIandJniteindexsets,andrelatetheautomatiityofSwiththeautomatiityofU.WeprovethatifUisanautomatisemigroupandSisnitelygeneratedthenSisanautomatisemigroup.IfSisanautomatisemigroupandthereisanentrypinthematrixPsuhthatpU1=UthenUisautomati.WealsoprovethatifSisaprex-automatisemigroup,thenUisaprex-automatisemigroup.1IntrodutionanddenitionsWeonsiderautomatisemigroupsasdenedin[3℄.Weareinterestedinthequestionofwhetherautomatiityofsemigroupsispreservedbyvarioussemigrouponstrutions.SomesemigroupsanbedesribedasReesmatrixsemigroupsoversemigroups.Inthisworkwestartwithanautomatisemi-groupU,andprovethataReesmatrixsemigroupS=M[U;I;J;P℄overUisautomatiwheneveritisnitelygenerated.ThisimpliesthatifasemigroupisnitelygeneratedandanbedesribedasaReesmatrixsemigroupoveranautomatisemigroupthenitisautomati.Weobservethat,bytheMainThe-1oremof[1℄,SisnitelygeneratedifandonlyifbothIandJarenitesets,UisnitelygeneratedandthesetUnVisnite,whereVistheidealofUgeneratedbytheentriesinthematrixP.Wealsoonsidertheonverseproblem:doestheautomatiityofSimplythatofU?WeprovethatthisistheasewhenSisprex-automatiorwhenthereisanelementpinthematrixPsuhthatpU1=U.Finally,weprovetheanalogousresultsforReesmatrixsemigroupswithzero.Westartbyintroduingthedenitionswerequire.TheReesmatrixsemi-groupS=M[U;I;J;P℄overthesemigroupU,withP=(pji)j2J;i2Iama-trixwithentriesinU,isthesemigroupwiththesupportsetIUJandmultipliationdenedby(l1;s1;r1)(l2;s2;r2)=(l1;s1pr1l2s2;r2)where(l1;s1;r1);(l2;s2;r2)2IUJ.WesaythatUisthebasesemigroupoftheReesmatrixsemigroupS.IfAisaniteset,wedenotebyA+thefreesemigroupgeneratedbyAonsistingofnonemptywordsoverAundertheonatenation,andbyAthefreemonoidgeneratedbyAonsistingofA+togetherwiththeemptyword.LetSbeasemigroupand:A!Samapping.WesaythatAisanitegeneratingsetforSwithrespettoiftheuniqueextensionoftoasemigrouphomomorphism:A+!Sissurjetive.Foru;v2A+wewriteuvtomeanthatuandvareequalaswordsandu=vtomeanthatuandvrepresentthesameelementinthesemigroupi.e.thatu=v.WesaythatasubsetLofA+isregularifthereisanitestateautomatonaeptingL.TobeabletodealwithautomatathataeptpairsofwordsandtodeneautomatisemigroupsweneedtodenethesetA(2;$)=((A[f$g)(A[f$g))nf($;$)gwhere$isasymbolnotinA(alledthepaddingsymbol)andthefuntionÆA:AA!A(2;$)denedby(a1:::am;b1:::bn)ÆA=8:if0=m=n(a1;b1):::(am;bm)if0m=n(a1;b1):::(am;bm)($;bm+1):::($;bn)if0mn(a1;b1):::(an;bn)(an+1;$):::(am;$)ifmn0:LetSbeasemigroupandAanitegeneratingsetforSwithrespetto:A+!S.Thepair(A;L)isanautomatistrutureforS(withrespetto2)ifLisaregularsubsetofA+andL=S,L==f(;):;2L;=gÆAisregularinA(2;$)+;andLa=f(;):;2L;a=gÆAisregularinA(2;$)+foreaha2A:Wesaythatasemigroupisautomatiifithasanautomatistruture.If(A;L)isanautomatistrutureforasemigroupSthenthereisanautomatistruture(A;K)suhthateahelementofShasauniquerepresentativeinK(see[3,Proposition5.4℄);wesaythat(A;K)isanautomatistruturewithuniqueness.Wesaythatasemigroupisprex-automatiorp-automatiifithasanautomatistruture(A;L)suhthatthesetL0==f(w1;w2)ÆA:w12L;w22Pref(L);w1=w2gisalsoregular,wherePref(L)=fw2A+:ww02Lforsomew02Ag:Formoredetailsonautomatisemigroupsthereaderisreferredto[3℄(in-trodution),[13℄(geometriaspetsandp-automatiity),[10℄,[11℄,[12℄(om-putationalanddeidabilityaspets)and[4℄,[5℄(otheronstrutions).2GeneralizedsequentialmahinesItisknownthatthefellow-travelerproperty,whihharaterizesautomatigroups,doesnotharaterizeautomatisemigroups.SowehavetousediretlythedenitionandworkwithregularlanguagesinsteadoftheCayleygraphtoprovethatasemigroupisautomati.Sineweareworkingwithsemigrouponstrutions,weusuallyhavetoonstrutautomatistruturesfromknownautomatistrutures.Forthatpurposeweusetheoneptofageneralizedsequentialmahine.Ageneralizedsequentialmahine(gsmforshort)isasix-tupleA=(Q;A;B;;q0;T)whereQ,AandBarenitesets,(alledthestates,theinputalphabetandtheoutputalphabetrespetively),isa(partial)funtionfromQAto3nitesubsetsofQB+,q02QistheinitialstateandTQisthesetofterminalstates.Theinlusion(q0;u)2(q;a)orrespondstothefollowingsituation:ifAisinstateqandreadsinputa,thenitanmoveintostateq0andoutputu.WeaninterpretAasadiretedlabelledgraphwithvertiesQ,andanedgeq(a;u)!q0foreverypair(q0;u)2(q;a).Forapath:q1(a1;u1)!q2(a2;u2)!q3:::(an;un)!qn+1wedene()=a1a2:::an;()=u1u2:::un:Forq;q02Q,u2A+andv2B+wewriteq(u;v)!+q0tomeanthatthereexistsapathfromqtoq0suhthat()uand()v,andwesaythat(u;v)isthelabelofthepath.Wesaythatapathissuessfulifithastheformq(u;v)!+twitht2T.ThegsmAinduesamappingA:P(A+)!P(B+)fromsubsetsofA+intosubsetsofB+denedbyXA=fv2B+:(9u2X)(9t2T)(q0(u;v)!+t)g:ItiswellknownthatifXisregularthensoisXA;see[9℄.Similarly,AinduesamappingA:P(A+A+)!P(B+B+)denedbyYA=f(w;z)2B+B+:(9(u;v)2Y)(w2uA&z2vA)g:Thenextlemmasassertsthat,underertainonditions,thismappingalsopreservesregularity.Lemma2.1LetA=(Q;A;B;;q0;T)beagsm,andletA:(AA)ÆA!AAbethein