资源描述：
《自由么半群上的广义前缀关系与极大无关语言》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第30卷第5期东北大学学报(自然科学版)Vol.30,No.52009年5月JournalofNortheasternUniversity(NaturalScience)May2009自由么半群上的广义前缀关系与极大无关语言刘群,李红(东北大学秦皇岛分校,河北秦皇岛066004)摘要:研究了与L-前缀关系无关的语言,把码的完全化构造方法推广为一般L-无关语言的完全化构造方法,并反过来用这种一般构造方法审视码的完全化·由于在码的完全化过程中,所涉及的关系与完全化之后的结果相关,从而必须引入各种技巧,运用L-无关语言完全化的一般构造方法可以阐明这种技巧的切入点,从而对码的各种完全化方法有一
2、个较清晰的认识·关键词:L-前缀关系;L-无关语言;极大L-无关语言;星号语言;具有延迟界d的延迟码;完全码;完全L-无关语言中图分类号:O157.4文献标识码:A文章编号:1005-3026(2009)05-0753-04GeneralizedPrefixRelationsonFreeMonoidsandMaximalIndependentLanguagesLIUQun,LIHong(NortheasternUniversityatQinhuangdao,Qinhuangdao066004,China.Correspondent:LIUQun,professor,E-mail:qli
3、u105@hotmail.com)Abstract:StudiesthelanguagesthatareindependentoftheL-prefixrelation.TheconstructionofthecompletionofcodesaregeneralizedasthatofL-independentlanguagesandontheotherhand,thelattercanbeusedtoexaminetheformer.Inthecompletingprocessofcodestherelationinvolvedisboundupwiththeresultofcom
4、pletion.Itisthereforenecessarytointroducevarioustechniquesintotheprocess,andhowtheyfunctioncanbeexpoundedbythegeneralconstructionofcompletionofL-independentlanguages.Inthiswayaclearunderstandingisavailabletovariousmethodsofcompletionofcodes.Keywords:L-prefixlanguages;L-independentlanguages;maxim
5、alL-independentlanguages;starlanguages;codeswithdecodingdelayd;completecodes;L-independentcompletelanguages**设A是以A为基的自由么半群,A的元系下的无关语言,由此得到比文献[3]的方法更为*[2]素称为字,A的子集称为语言·在语言的研究简单的延迟码的完全化方法,进一步又得到同*中,广泛地运用自由么半群A上的二元关系,例时有右延迟界n和有左延迟界m的双向延迟码[4]如长度关系,前缀关系,后缀关系,因子关系的完全化方法·本文讨论一般广义前缀关系下[1]等,某种关系下的无关语言的研究
6、是语言中的的无关语言及其完全化,把一些码的完全化构造重大课题,例如前缀关系下的无关语言构成前缀方法推广为这类无关语言的完全化构造方法,同[2]码这个应用频繁的码类·1999年,Zhang等人时,反过来,用L-无关语言完全化的一般原则来提出了一种广义前缀关系,所谓L-前缀关系,其说明一些码的完全化构造·*中L A是某个语言:x≤Ly如果y∈xL于是下面是本文涉及的术语和记号:*+*通常的前缀关系就是A-前缀关系·这种广义A=A-{1},为简便起见,以下类似情况**前缀关系的重要意义在于它揭示了具有延迟界d写作A=A-1·d*A*-1的延迟码X就是在(XA)(X)-前缀关对收稿日期:200
7、7-03-07基金项目:国家自然科学基金资助项目(10471099)·作者简介:刘群(1959-),男,江西宜春人,东北大学秦皇岛分校教授·754东北大学学报(自然科学版)第30卷*X,Y A,XY={xy
8、x∈X,y∈Y},w2∈Z且w1≠w2,有四种情形:①w1,w2∈X·-1*XY={w∈A
9、存在y∈Y使得wy∈X}·因X是L-无关语言,显然w1≠Lw2·②w1,w2**如果L A满足L=L,即在连接运算下∈Y·如果w1=Lw2,不妨假定
