资源描述：
《error-correction and finite transductions》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、Error-CorrectionandFiniteTransductionsChristopherL.McAloneyMarch2004ExternalTechnicalReportISSN-0836-0227-2004-476DepartmentofComputingandInformationScienceQueen’sUniversityKingston,Ontario,CanadaK7L3N6DocumentpreparedMarch11,2004AbstractRecently,therehasbeenarenewedinter
2、estinthedetectionandthecorrectionoferrorswhichoccurindatasentacrossnoisycommunicationchannels.Weconsidertheproblemsoferror-detectionanderror-correctionfromtheperspectiveofformallanguages,inwhichthetransmitteddataarestringsofsymbolsfromanarbitraryalphabet.Wediscussindetail
3、aparticularclassoferrorchannels,theSIDchannels,inwhichthechannelmaycauseuptoksubstitution,insertionordeletionerrorsinanylconsecutivesymbolsoftheinputword.Inthisthesis,wewillexaminetheSIDchannelsinsomedepthand,usingtoolsfrommetricanalysis,defineameasureofdistancewhichcanbeu
4、sedformallytomeasurethenumberoferrorsbetweenanypairofwords.Wethenshow,throughageneralizedfinitetransducerconstructionforSIDchannelsthat,providedtheinputlanguageforthechannelisregular,theunionoftheneighbourhoodsofwordsinthelanguagewithrespecttoourdistancemeasureisalsoregula
5、randthustheoutputlanguagefromthechannelisitselfaregularlanguage.Asmotivationforourwork,wediscusstheStatechartslanguageindepthanddefineawrittennotationwhichcanbeusedtoformallydiscussarestrictedclassofstatecharts.Usingthisnotation,weprovideastatechartconstructionwhichcanbeus
6、edtoacceptthelanguageoutputbyaparticulartypeorerrorchannel.AcknowledgementsIwouldliketothankmysupervisor,Dr.KaiSalomaa,withoutwhoseguidanceandsupportthisthesiswouldnothavebeenpossible.ManythankstoAmandaandmyparents,NancyandWilliamMcAloney,fortheirsupportandencouragement,a
7、ndtoallotherswhohaveinfluencedmythoughtsoverthecourseofthewritingofthisthesis,fromconceptiontocompletion.1IntroductionAutomaticerror-correctiontechniqueshavebeenreceivingalotofattentioninrecentyears.Withtherapidoverpopulationoftheinternet,muchresearchhasbeendevotedtofinding
8、newwaysinwhichlargeamountsofinformationcanbeaccuratelytransmittedbetweentwopoints.Asmoreofficesloo
