資源描述：
《error-correction and finite transductions》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在行業(yè)資料-天天文庫。
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,de?neameasureofdistancewhichcanbeu
4、sedformallytomeasurethenumberoferrorsbetweenanypairofwords.Wethenshow,throughageneralized?nitetransducerconstructionforSIDchannelsthat,providedtheinputlanguageforthechannelisregular,theunionoftheneighbourhoodsofwordsinthelanguagewithrespecttoourdistancemeasureisalsoregula
5、randthustheoutputlanguagefromthechannelisitselfaregularlanguage.Asmotivationforourwork,wediscusstheStatechartslanguageindepthandde?neawrittennotationwhichcanbeusedtoformallydiscussarestrictedclassofstatecharts.Usingthisnotation,weprovideastatechartconstructionwhichcanbeus
6、edtoacceptthelanguageoutputbyaparticulartypeorerrorchannel.AcknowledgementsIwouldliketothankmysupervisor,Dr.KaiSalomaa,withoutwhoseguidanceandsupportthisthesiswouldnothavebeenpossible.ManythankstoAmandaandmyparents,NancyandWilliamMcAloney,fortheirsupportandencouragement,a
7、ndtoallotherswhohavein?uencedmythoughtsoverthecourseofthewritingofthisthesis,fromconceptiontocompletion.1IntroductionAutomaticerror-correctiontechniqueshavebeenreceivingalotofattentioninrecentyears.Withtherapidoverpopulationoftheinternet,muchresearchhasbeendevotedto?nding
8、newwaysinwhichlargeamountsofinformationcanbeaccuratelytransmittedbetweentwopoints.Asmoreo?cesloo
