项重写系统和自由幺半群

林沐辰,朱志成,张毅

(1.南京信息工程大学数学与统计学院,江苏 南京 210044;2.兰州大学数学与统计学院,甘肃 兰州 730000)

1 引言

抽象重写系统是由文献[1]首次提出的.文献[2-4]将抽象重写系统的对象变成了一些项,称之为项重写系统,并考虑了它的性质和广泛的应用,例如软件工程,计算机代数,Gr¨obner-Shirshov基础[5-10],Boolean理论[12-14]和群理论[11].换言之,项重写系统可以成功地应用于计算机科学、理论计算机科学和数学.

项重写系统是由一组等式定义的项上的等价类的重写组成.研究项重写系统可能面临的主要问题之一是对具有汇合或终止等基本性质的重写系统类的刻画.终止的性质保证了任意项在重写法则之下都可以终止于一个规范型.此外,如果项重写系统是汇合的,那么规范型是唯一的.因此,无论重写法则使用的是哪一种序关系,一个既终止又汇合的项重写系统保证了它具有唯一规范型的特性,参见文献[15-18].这些论文对终止和汇合及其相关性质进行了全面研究.终止性和汇合性这两个性质是极其重要的,本文将基于自由幺半群上的重写系统对它们进行广泛研究.

项重写也可以在Herbrand-G¨odel可计算性中找到.后来,项重写系统的概念以其目前的形式被提出,并被用于实现规格分析、可计算性理论、字问题和定理证明.随着里程碑论文中完成方法的出现,文献[18]为这个领域带来了新的生机.Knuth-Bendix程序操作重写系统,这个十分关键.这些系统被用来简化字问题,试图解决特定的有限群或有限呈现的幺半群的字问题.

终止与汇合问题在重写系统的研究中起着不可或缺的作用.研究这些问题的一种方法是将注意力限制在简单类型的代数结构上,如幺半群,这已经被非常成功地运用在文献[19-21]中.另外,要强调一下,在过去的几十年里,人们对半群和幺半群上的重写系统进行了深入的研究.文献[22]研究了中国幺半群,证明了中国幺半群具有收敛的重写系统.对于自由幺半群A*中的每一个元素,都有一个算法来求其规范型.因此,中国幺半群的字问题是可解的.给定一个具有有限多左右理想的正则半群,如果每个极大子群都能用一个有限的完备重写系统表示,那么该半群也是如此.这一结果由Gray和文献[23]证明.文献[24]利用杨表计数的组合性质,构造了相应的Plactic幺半群的有限完备重写系统.

本文沿着这条线,利用重写系统的理论,研究了收敛重写系统与自由幺半群的商截面的关系.作为应用,分别得到了由三个元素生成的Plactic幺半群和中国幺半群的商截面.

论文的结构安排如下.在第2章中,首先回顾了项重写系统的一些基本定义和符号.接下来,研究了专门用于自由幺半群上的项重写系统的新结果,得到了所使用的重写系统的一些基本结果.特别地,应用重写系统的方法给出了一个统一的方法来研究收敛重写系统和自由幺半群商截面之间的关系.第3章分别研究了由3个元素生成的Plactic幺半群(定理4.1)和中国幺半群(定理4.2)的商截面.

2 自由幺半群上的项重写系统

本节首先介绍一些基于自由幺半群的项重写系统的一些符号和结果[25-26].现在,把项重写系统与集合A生成的自由幺半群A*上的一个二元关系联系起来.

定义2.1[27]设A是集合,A+是字母表A中所有限非空字a1a2···am的集合.A+上的一个二元运算定义为

其中m,n∈N.关于这个二元运算,称A+为A上的自由半群.若在A+中添加单位1(作为空字),则得到A上的自由幺半群,记为A*.

定义2.2设A是集合,S⊆A*×A*,≤是A*上的线性序.

(a)定义

称系统(A*,ΠS)为与S有关的A*上的项重写系统.称ΠS中的元素(u,v)为ΠS的一个重写法则,记为u→v.

(b)称f∈A*一步重写到g∈A*,记为或者更详细地若存在a,b∈A*和u→v∈S,使得f=aub且g=avb.

(c)称f∈A*关于ΠS n步(n≥1)重写到g∈A*,记为若存在f0,f1,···,fn∈A*,使得fi/=fi+1,i=0,···,n-1且

若存在g∈V,n≥1,使得则称f∈V为可约的.否则称f为不可约的或者在规范型中.

(d)记二元关系的自反传递闭包关系→ΠS(作为A*上的一个二元关系)为若则称f关于ΠS重写为g,并称f是g的前任.记P(g)为g的所有前任的全部集合.因此g∈P(g).

(e)称f和g是汇合的,记为若存在h∈A*,使得则

定义2.3设A是集合,S⊆A*×A*,≤是A*上的线性序.称项重写系统(A*,ΠS)是

(c)收敛或者完备的,如果它既是终止的又是汇合的.

关于重写系统的一个众所周知的结果是Newman′s引理[25].

引理2.1(Newman)终止项重写系统是汇合的当且仅当它是局部汇合的.

这里需要文献[28]中的以下定义和引理.

定义2.4[28]称A*上线性序≤为

(a)可容许的,如果对于任意u,v,x,y∈A*,u≤v可得xuy≤xvy.

(b)良构造的,如果不存在无限形式的链x0＞x1＞x2＞···,其中x0,x1,···∈A*.在这种情况下,称≤为可容许的.

容许良序在重写系统中起着重要作用,见下面引理.

引理2.2[28]设A是集合,S⊆A*×A*,≤是A*上的线性序.则下面两条陈述是等价的:

(a)项重写系统(A*,ΠS)是终止的;

(b)线性序≤是A*上的一个容许良序.

3 收敛的项重写系统和截面

本节将刻画自由幺半群A*上的收敛项重写系统和A*的商截面之间的关系.

对于一个二元关系S⊆A*×A*,记〈S〉为S生成的同余.每个同余〈S〉都有一个相应的商结构A*/〈S〉,它是由该关系的同余类组成.

定义3.1设A是集合,S⊆A*×A*.若对于〈S〉的每一个同余类A,恰好存在唯一的元素w∈W使得w∈A,则称A*的子集W为A*/〈S〉的截面.

定义3.2设U是半群且U1是具有邻接单位的半群.设S是U上二元关系.若c,d∈U使得c=xay,且d=xby,对于U1中一些元素x,y,其中(a,b)或(b,a)也属于S,则可以说c通过一个基本S-传递与d相连.

这里需要下列引理.

引理3.1[27]设S是半群U上的关系,并且a,b∈U.则(a,b)∈〈S〉当且仅当a=b或者存在一个基本S-传递序列a=z1-z2-···-zn=b,n≥1,连结a到b,其中〈S〉是由S生成的同余.

引理3.2设A是集合,S⊆A*×A*,≤是A*上线性序.如果那么(f,g)∈〈S〉.

证明如果f=g,那么显然(f,g)∈〈S〉.假设.设n≥1是使得的最小数.对n作归纳来证明这一结果.对于n=1的归纳起点,根据定义2.2,存在a,b∈A*和(u,v)∈ΠS使得f=aub且g=avb,因此(f,g)∈〈S〉.对于n＞1的归纳步骤,令

根据归纳假设,可得(f,h)∈〈S〉和(h,g)∈〈S〉,利用同余的传递性,可得(f,g)∈〈S〉.

设≤是A*上的线性序.对于由A*上的二元关系S生成的同余〈S〉,定义

对于公式(1)中给出的项重写系统,记:

它是由A*的在(A*,ΠS)的规范型中的元素构造的集合.

引理3.3设A是集合,S⊆A*×A*,≤是A*上的线性序.

(a)若(A*,ΠS)是汇合的,则Pm(〈S〉)∩Irr(S)=Ø.

(b)若(A*,ΠS)是终止的且Pm(〈S〉)∩Irr(S)=Ø,则(A*,ΠS)是汇合的.

证明(a)若Pm(〈S〉)∩Irr(S),则设w∈Pm(〈S〉)∩Irr(S).因为w∈Irr(S),w在规范型中.又因为w∈Pm(〈S〉),则存在v∈A*使得

由引理3.1,对于任意n≥1和zi∈A*,1≤i≤n,存在一个基本S-传递序列w=z1-z2-···-zn=v,连接w到v.则对任意的1≤i≤n-1,

由等式(1),因为w=z1在规范型中,所以有

若

则由可得v＞w,这与等式(3)中w＞v矛盾.因此存在最大值i,1≤i≤n-1使得

并且通过可得v＞w,再次与方程(3)中的w＞v矛盾.所以zi+1,即,当i≤n-2,存在zi+2,使得或者对于前一种情况,通过对于后一种情况,因为是一个分叉,w在规范型中,则由(A*,ΠS)是汇合的可得继续这个过程,最后可得到和v＞w,这与等式(3)中w＞v矛盾.

(b)假设有相反的情形(A*,ΠS)是不汇合的.则存在分叉是不可汇合的.因为(A*,ΠS)是终止的,所以存在u1,v1∈Irr(S),使得u11,由引理3.2,有(w,u1),(w,v1)∈〈S〉,因此(u1,v1)∈〈S〉.从而u1∈Pm(〈S〉)或者v1∈Pm(〈S〉),这两种情形都与Pm(〈S〉)∩Irr(S)=Ø矛盾.

引理3.4设A是集合,S⊆A*×A*,≤是A*上容性良序.则

证明因为Pm(〈S〉),Irr(S)⊆A*,由此可见Pm(〈S〉)∪Irr(S)⊆A*.相反地,设u∈A*.由引理2.2可知(A*,ΠS)是终止的,于是u有一个规范型v∈Irr(S),使得若u=v,则u∈Irr(S)⊆Pm(〈S〉)∪Irr(S),得证.假设u/=v.由引理3.2,可得(u,v)∈〈S〉.因为≤是容许的,所以v＜u,因此

证毕.

引理3.5设A是集合,≤是A*上的容性良序.对于〈S〉的每一个同余类A,有

证明由引理2.2可得项重写系统(A*,ΠS)是终止的.设b∈A.则存在a∈Irr(S)使得由引理3.2,有(b,a)∈〈S〉,从而a∈A.因此且因为由b∈P(a)可得

反之,对任意元素a∈A,由引理3.2可得P(a)⊆A,从而证毕.

引理3.6设A是集合,S⊆A*×A*,≤是A*上的容性良序.对于〈S〉的每一个同余类A,若(A*,ΠS)是汇合的,则|A∩Irr(S)|=1.

证明由引理3.5,可得|A∩Irr(S)|≥1.假设有相反的情况|A∩Irr(S)|≥2.令

且|I|≥2,会出现两种情形.

情形1:对于一些i,j∈I且在这种情况下,存在为一个分叉.因为ai,aj∈Irr(S)且aiaj,所以ai和aj不可汇合,这与(A*,ΠS)是汇合的相矛盾.

情形2:对任意i,j∈I且因为(ai,aj)∈〈S〉,针对引理3.1,存在一个基本S-传递序列ai=z1-z2-···-zn=aj,连接ai到aj,n≥1,zk∈A*,1≤k≤n.类似于引理3.3(a)的证明,有

注意到ai∈Irr(S).因此可以选择ℓ:=max{k|zk∈P(ai),1≤k≤n}.若ℓ=n,则aj=zn∈P(ai),因此aj∈P(ai)∩P(aj),这与P(ai)∩P(aj)=Ø矛盾.假设1≤ℓ＜n.则

定理3.1设A是集合,S⊆A*×A*,≤是A*上的容性良序.则以下陈述是等价的.

(a)(A*,ΠS)是收敛的.

(b)(A*,ΠS)是汇合的.

(d)Irr(S)是A*/〈S〉的截面.

证明因为≤是A*上的容性良序,由引理2.2知(A*,ΠS)是终止的.所以(a)和(b)是等价的.由引理3.3,引理3.4可知(b)和(c)的等价性.

((b)⇒(d))假设(A*,ΠS)是汇合的.根据引理3.6,Irr(S)得每一个同余类恰只有一个元素,所以Irr(S)是A*/〈S〉的截面.

((d)⇒(b))假设(A*,ΠS)是不汇合的.则存在一个分叉是不可汇合的.因为(A*,ΠS)是终止的,可以假设且有u1,v1∈Irr(S),u11,所以根据引理3.2,有(w,u1),(w,v1)∈〈S〉,所以(u1,v1)∈〈S〉.因此在同一个同余类中Irr(S)包含两个元素u1和v1,这与Irr(S)是A*/〈S〉的截面矛盾.证毕.

4 应用

在本节中,分别给出由三个元素生成的Plactic幺半群[10]和中国幺半群[22]的截面.

定义4.1设A={x1,x2,x3}.由A生成的Plactic幺半群是A*模去同余〈S〉的商,其中S是Knuth关系:

扩展生成元的集合A:x1＜x2＜x3上的序,为A*装配一个带权字典序≤wl.文献[10]表示与上述S相关的项重写系统是不收敛的;但在增加三个额外的重写法则后,它是收敛的.记:

关联S的项重写系统(A*,ΠS)是收敛的.

引理4.1[10]用上面的符号,

(a)Plactic幺半群上的项重写系统(A*,ΠS)是收敛的.

(b)项重写系统(A*,ΠS)的规范型的集合是

作为该引理的直接结果,有

定理4.1采用上述符号,规范型的集合Irr(S)是秩为3的Plactic幺半群的截面.

证明由定理3.1和引理4.1可得.

接下来,给出了中国幺半群的截面.

定义4.2设A={x1,···,xn}.A上的中国幺半群是自由幺半群A*模掉中国同余〈S〉的商,其中

使用A*上的加权字典序≤wl,它扩展了生成元上的序:x1＜x2＜···＜xn.与上述S相关的项重写系统是不收敛的;但在添加一个新的重写法则[22]后,它是收敛的.记:

引理4.2[22]采用上面的符号,中国幺半群的项重写系统(A*,ΠS)是收敛的.

作为一个直接的结果,有

定理4.2采用上述符号,规范型的集合:是中国幺半群的截面.

证明由定理3.1和引理4.2可得.