文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Received (Day Month Year)
侵权投诉

Received (Day Month Year)

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

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email