一类后缀码的代数性质

田径,胡钢

(西安理工大学理学院,陕西 西安 710054)

一类后缀码的代数性质

田径,胡钢

(西安理工大学理学院,陕西 西安 710054)

利用自由含幺半群X∗上的一个偏序关系,介绍了一类特殊的后缀码.通过定义这类后缀码上的两种二元运算,研究了这类后缀码的代数性质.证明了该子类在这两种运算下形成一个加法导出是半格的半环,并且满足吸收律.从而提供了一个满足吸收律的半格序半群的例子.

后缀码;半格序;半环

1 引言与预备知识

设X为非空字符集,称为字母表.称X中有限多个字符形成的字符串为X上的字.特别的,称不含任何字符的字为空字,记为ε.设w为字,记lg(w)为字w中包含字母的个数(同一字母出现多次,按重数计算).若x∈X,则lg(xx)=2.显然lg(ε)=0.称由若干字形成的集合(有限或无限)为形式语言(或语言).进一步,记X∗为X上字的全体.对任意的x,y∈X∗,记xy为字x和y的并置,即:

xy=x1x2···xny1y2···ym,其中x=x1x2···xn,y=y1y2···ym,n,m为正整数.

那么,xy∈X∗.易见,并置是X∗上的二元运算.这样X∗在并置运算下成为一个幺半群,称为由X生成的自由幺半群[1],并称X+=X∗{ε}为由X生成的自由半群.

设A⊆X∗是一个非空语言.若对于任意的字x1,x2,···,xn,y1,y2,···,ym∈A,总有成立,则称A为码[2].

设A⊆X∗是一个非空语言.令w,u∈A.若存在x∈X∗使得w=xu,则称u是w的一个后缀.若A中任意一个字都不是其他字的后缀,则称A为后缀码.容易验证后缀码是码[2].

在X∗上定义偏序关系“≤s”如下:

容易发现非空语言A是后缀码当且仅当A中任意两个元素在偏序关系“≤s”下是不可比较的.文献[3]中给出了“≤s”是偏序关系的证明和更多用偏序关系定义的码.

另一方面,对于一个(2,2)-型代数(T,+,·),如果(T,+)和(T,·)是半群并且满足分配律,那么就称(T,+,·)是半环[4].若半环(T,+,·)还适合恒等式x+x≈x和x+y≈y+x,就可以在半群(T,·)上定义一个半格序,使之成为偏序半群.那么二元运算“+”就可以看成取两个元素的上确界(或下确界).此时,也称(T,+,·)为半格序半群.由于半格序半群是一种很常见的代数结构,所以被半群学者广泛研究(见文献[6-8]).

记S(X)(Sf(X))为字母表X上后缀码(有限后缀码)的全体.文献[3]详细论述了S(X)作为2-型代数的性质,证明S(X)关于集合的乘法运算“◦”成为自由含幺半群,并进一步研究了后缀码的一些子类和它们的代数性质.文献[9]利用X∗上的嵌入序定义了超码之间加法运算“+”,使全体超码在集合乘法和加法的意义下成为半环且适合恒等式1+x≈x.

作为文献[3,9]的延续,第二节利用X∗上的偏序关系得到有限后缀码的一个子类Sw(X).并讨论了它在集合的乘法运算和并运算下的性质.第三节利用集合的乘法运算和并运算定义了这一子类上的两个新的二元运算—乘法和加法,讨论Sw(X)代数性质.结果表明(Sw(X),+,·)是一个满足吸收律的半格序半群.

2 正规后缀码

设ρ为X∗上的二元关系,H⊆X∗.若对H 中任意两个不同的元素u,v都有(u,v)/∈ρ,则称H是X∗上ρ的无关集.记X∗上所有ρ的无关集形成的集族为Hρ(X).称X∗上的二元关系ρ是严格的[10],如果对任意的u,v∈X∗有:

(i)uρu且ερu;

(ii)uρv⇒lg(u)≤lg(v);

(iii)uρv,lg(u)=lg(v)⇒u=v.

显然,上一节中提到的二元关系“≤s”是严格的并且H≤s(X)=S(X).现定义X∗上的二元关系“≤w”如下:

(∀u,v∈X∗)u≤wv⇔u=v或(∃z∈X+,x,y∈X∗)lg(x)

定义2.1设A⊆X∗.若A是X上的≤w的无关集,则称A是X上正规后缀码.记X上的全体有限正规后缀码形成的集族为Sw(X).

由“≤w”的定义可知,

进一步,u≤wv当且仅当下面两个条件成立:

(i)当 lg(u)=lg(v)时,u=v;

(ii)当 lg(u)

这样,容易验证二元关系“≤w”是严格的.此外,由严格二元关系定义中的(i)和(iii)知“≤w”是自反的和反对称的.下面证明“≤w”是传递的.

设 t≤wu,u≤wv.若 lg(t)=lg(u)=lg(v),则 t=u=v,那么 t≤wv;若 lg(t)/=lg(u)或 lg(u)/=lg(v),则 lg(t)

性质 2.1“≤w”是X∗上的严格偏序关系并且≤s⊆≤w.

证明只需证明 ≤s⊆≤w.设 u,v∈X∗,u≤sv.那么 (∃x∈X∗)使得 v=xu.故有lg(v)≤lg(u).于是当lg(u)=lg(v)时,由v=xu知x=ε,故u=v.当lg(u)

关于严格二元关系,文献[10]给出了下面的结果.

引理 2.1[10]令ρ1,ρ2是X∗上的严格二元关系.那么

由性质2.1和引理2.1可知H≤w(X)⊆H≤s(X).因为H≤s(X)=S(X),所以正规后缀码是后缀码.从而Sw(x)⊆S(X).关于二元关系与码的联系的更多内容,参见文献[3,10].

例 2.1设X={a,b}.令A={aa,ba,b},B={ba,baa}.由于A是“≤w”无关的,所以A是正规后缀码.又因为ba≤wbaa,所以B不是正规后缀码.但B是“≤s”无关的,故B是后缀码.

设A⊆X+是非空有限语言.分别记A中所有在偏序关系“≤w”下的极小元和极大元形成的集合为L(A)和U(A),即

根据正规后缀码的定义可直接得到以下结果.

性质2.2设A⊆X+是非空有限语言.那么

(i)L(A)和U(A)都是正规后缀码;

(ii)A是正规后缀码当且仅当L(A)=U(A)=A.

设A⊆X+.记A中字长最短的元素形成的集合为A,即

性质2.3设A⊆X+是非空语言.那么是正规后缀码.

文献[3]证明如果A和B都是后缀码,那么A◦B也是后缀码.其中“◦”是通常的集合的乘法运算,其定义如下:

但下面的例子表明,对于正规后缀码,类似的结果一般并不成立.

例2.2设X={a,b}.令A={ab,baa},B={b}.显然A和B都是正规后缀码.但A◦B={abb,baab}不是正规后缀码.注意到,集合A∪B={ab,baa,b}甚至不是后缀码.

引理2.2设那么是正规后缀码.

证明反证法.假设不是正规后缀码,则必然存在使a1b1≤wa2b2,

其中a1,a2∈A;b1,b2∈B.若lg(a1b1)=lg(a2b2),则有a1b1=a2b2.因为lg(a1)=lg(a2),所以b1=b2,这与B是正规后缀码矛盾.

另一方面,若lg(a1b1)

设A,B∈X+.由性质2.3知和是正规后缀码,又由引理2.2,知是正规后缀码.进一步,容易证明下面的引理2.3.

引理2.3若A,B∈X+,则

设A,B∈X+.由性质2.2知L(B)是正规后缀码,又由引理2.2知也是正规后缀码.并且有

引理2.4若A,B⊆X+,则

证明设A,B⊆X+.若则存在使由于是语言中的极小元,那么b是B中的极小元,即b∈L(B).(事实上,若b/∈B,则存在不同于b的b′∈B,使得b′≤wb,于是这就意味着矛盾.)故从而有

关于集合的并运算,有下面的结果.

引理2.5若B,C⊆X+,则

证明设B,C⊆X+.显然L(B∪C)⊆B∪C,那么

3 正规后缀码的代数性质

在全体有限正规后缀码形成的集族Sw(X)上定义乘法运算“·”与加法运算“+”如下:

由于这两个二元运算都是封闭的,那么(Sw(X),+,·)成为一个(2,2)-型代数.这一节将讨论二元运算“·”,“+”的性质并利用相关结果证明(Sw(X),+,·)是一个半环.首先讨论乘法运算的性质.

性质3.1设A,B⊆Sw(X).那么

证明设A,B∈Sw(X).令因为对任意的和b∈B,总有那么所以于是再由引理2.2和性质2.2知故

性质 3.2(Sw(X),·)是半群.

证明只需证明乘法“·”是结合的.对任意的A,B,C∈Sw(X),有

接下来讨论加法运算的性质.对于任意的A,B∈Sw(X),根据集合的并运算“∪”的幂等性和交换性得到

这就说明加法运算是幂等的和交换的.进一步,有

性质 3.3(Sw(X),+)是半群.

证明只需证明加法“+”是结合的.对任意的A,B,C∈Sw(X),总有

成立.为了确定集合A∪B∪C在偏序关系“≤

w

”下的极小元.可先找出A∪B中的所有极小元,即L(A∪B).然后再找出集合L(A∪B)∪C中的所有极小元L(L(A∪B)∪C),于是L(A∪B∪C)=L(L(A∪B)∪C)成立.这就说明

同理可证,L(A∪B∪C)=A+(B+C),那么

故“+”是结合的,从而(Sw(X),+)是半群.

为了说明(Sw(X),+,·)是半环,只需再证分配律成立,即对任意的A,B,C∈Sw(X),总有

成立.因为

所以(1)式成立.又因为

所以(2)式成立.

综上所述,(Sw(X),+,·)是半环并且它的加法导出(Sw(X),+)是半格.此外,还可以证明以下结果.

性质3.4对任意的A,B,C∈Sw(X),有B·A+A=A成立.

证明设A,B,C∈Sw(X).那么

这样,(Sw(X),+,·)是一个适合吸收律yx+x≈x的半格序半群.

[1] Howie J.Fundamentals of Semigroup Theory[M].Oxford:Clarendon Press,1995.

[2] Berstel J,Perrin D,Reutenauer C.Codes and Automata[M].Cambridge:Cambridge University Press, 2010.

[3] Ito M,J¨urgensen H,Shyr H J,Thierrin G.Out fi x and in fi x codes and related classes of languages[J].Journal of Computer and System Sciences,1991,43(3):484-508.

[4] Golan J.The Theory of Semirings,with Applications in Mathematics and Theoretical Computer Science[M]. Harlow:Longman Scienti fi c and Technical,1992.

[5] Burris S,Sankappanavar H P.A Course in Universal Algebra[M].New York:Springer-Verlag,1981.

[6] Zhao X.Idempotent semigroups with a commutative additive reduct[J].Semigroup Forum,2002,64(2):289-296.

[7] Martin K,Libor P.On varieties of semilattice-ordered semigroups[J].Semigroup Forum,2005,71(1):27-48.

[8] Sen M K,Bhuniya A K.On semirings whose additive reduct is a semilattice[J].Semigroup Forum, 2011,82(1):131-140.

[9] Wang Z,Liang F,He Y,Yang D.Semiring structures of some classes of hypercodes[J].Journal of Automata, Languages and Combinatorics,2009,14(3):259-272.

[10] Shyr H J.Lecture notes:Free Monoids and Languages[M].3rd ed.Oxford:Hon.Min.Book Company, 2001.

On a subclass of suffix codes

Tian Jing,Hu Gang
(School of Scince,Xi′an University of technology,Xi′an 710054,China)

We introduce a subclass of suffix codes in terms of a partially order on X∗.By using two binary operations de fi ned on this subclass,we investigate the algebraic properties of it.It is shown that equipped with these two binary operations,this subclass forms a semiring whose addictive reduct is a semilattice.Also,we prove that this algebra satis fi es absorbtion law.Thus,we provide an example of semilattice-ordered semigroup satisfying absorbtion law.

suffix codes,semilattice order,semirings

O236.2

A

1008-5513(2014)04-0360-07

10.3969/j.issn.1008-5513.2014.04.005

2014-03-20.

国家自然科学基金(51305344);陕西省自然科学基金(2014JQ1014).

田径(1979-),博士,讲师,研究方向：自动机和形式语言理论.

2010 MSC:20M35