Communicated by [editor] Generalizing results of Otto & Ruˇskuc, this paper shows that every finitely generated submonoid of a monoid presented by a confluent finite special rewriting system admits an automatic structure that is simultaneously rr-, ?r-, r
InternationalJournalofAlgebraandComputation
cWorldScienti cPublishingCompany
ONMONOIDSPRESENTEDBYREWRITINGSYSTEMSANDAUTOMATICSTRUCTURESFORTHEIRSUBMONOIDS
ALANJ.CAIN
SchoolofMathematicsandStatistics,UniversityofStAndrews,NorthHaugh,
StAndrews,FifeKY169SS,UnitedKingdom.
alanc@mcs.st-andrews.ac.uk
Received(DayMonthYear)
Revised(DayMonthYear)
Communicatedby[editor]
GeneralizingresultsofOtto&Ruˇskuc,thispapershowsthatevery nitelygeneratedsubmonoidofamonoidpresentedbyacon uent nitespecialrewritingsystemad-mitsanautomaticstructurethatissimultaneouslyrr-, r-,r -,and -automatic;andthatevery nitelygeneratedsubmonoidofamonoidpresentedbyacon uentregularmonadicrewritingsystemadmitsanautomaticstructurethatissimultaneouslyrr-and -automatic.Analgorithmisgiventodecidewhetherthemonoidpresentedbyacon- uentmonadic niterewritingsystemis r-orr -automatic.Shouldsuchamonoidbe r-orr -automatic,therewritingsystem’slanguageofnormalformwordsformspartofsuchanautomaticstructure.Theseresultsareappliedtoyieldanswerstosomehithertoopenquestionsandtorecoverandgeneralizeestablishedresults.
Keywords:Automaticmonoids;stringrewritingsystems;submonoids.
MathematicsSubjectClassi cation:20M05,68Q45
1.Introduction
Otto&Ruˇskuc[18]examinedthequestionofwhethermonoidspresentedbyvar-iousspeciesofrewritingsystemadmitautomaticstructures.Theyestablishedahierarchyofrewritingsystemsintermsofthenotionsofautomatismobeyedbythecorrespondingautomaticstructures.[Thefourpossiblenotionsofautomatism, rstdiscussedbyHo mann&Thomas[16],dependonwhetherthemultiplierlanguagesstoreinformationaboutmultiplicationontherightorontheleft,andonwhetherstringsofdi eringlengtharepaddedontherightorontheleft.]Inparticular,Otto&Ruˇskucshowedthatamonoidpresentedbya nitespecialcon uentrewrit-ingsystemadmitsanautomaticstructurethatissimultaneouslyautomaticinallfoursenses,butthatinpassingtorewritingsystemsthatareeitherregular(ratherthan nite)ormonadic(ratherthanspecial),oneretainsingeneralonlyright-rightandleft-leftautomatism(thatis,paddingandmultiplicationmustbeonthesame
1
Revised (Day Month Year) 暂无评价 18页 免费 Received Day Month Day R... 暂无评价 21页 免费 Received Year Month Day ... 暂无评价 4页 免费 ...
scienti?que, 59655 Villeneuve d’Ascq Cedex - France a e jourdan@li?.fr http://<www.li?.fr/ jourdan> Received (Day Month Year) Accepted (Day ...
965 8580 Japan roman@u-aizu.ac.jp Received (Day Month Year) Revised (Day Month Year) Accepted (Day Month Year) Communicated by (xxxxxxxxxx) The ...
Brazil emilio@impa.br lhf@impa.br Received (Day Month Year) Revised (Day Month Year) Accepted (Day Month Year) Communicated by (xxxxxxxxxx) We ...
Revised (Day Month Year) 暂无评价 18页 免费 Received Day Month Day R... 暂无评价 21页 免费 Received Year Month Day ... 暂无评价 4页 免费 ...
Received (Day Month Year... 暂无评价 15页 免费 Received (Day Month Year... 暂无评价 16页 免费 Received Day Month Year ... 暂无评价 20页 免费 ...
免费 Revised (Day Month Year) 暂无评价 18页 免费 Received Day Month Day R... 暂无评价 21页 免费 Received Year Month Day ... 暂无评价 4页 免费...
NW Calgary, Alberta, T2N 1N4, Canada blob@cpsc.ucalgary.ca erwin@erwindegroot.nl http://pages.cpsc.ucalgary.ca/ blob/ Received (Day Month Year) ...
Received Year Month Day ... 暂无评价 4页 免费 Received (Day Month Year... 暂无评价 15页 免费 Received (Day Month Year... 暂无评价 20页 免费 ...
YEAR-MONTH-DAY 函数_计算机软件及应用_IT/计算机_专业资料。今日推荐 ... Revised (Day Month Yea... 暂无评价 18页 免费 Received (Day Month Ye....
热门文档