項重寫系統(tǒng)和自由幺半群

林沐辰,朱志成,張毅

(1.南京信息工程大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院,江蘇 南京 210044;2.蘭州大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院,甘肅 蘭州 730000)

1 引言

抽象重寫系統(tǒng)是由文獻(xiàn)[1]首次提出的.文獻(xiàn)[2-4]將抽象重寫系統(tǒng)的對象變成了一些項,稱之為項重寫系統(tǒng),并考慮了它的性質(zhì)和廣泛的應(yīng)用,例如軟件工程,計算機(jī)代數(shù),Gr¨obner-Shirshov基礎(chǔ)[5-10],Boolean理論[12-14]和群理論[11].換言之,項重寫系統(tǒng)可以成功地應(yīng)用于計算機(jī)科學(xué)、理論計算機(jī)科學(xué)和數(shù)學(xué).

項重寫系統(tǒng)是由一組等式定義的項上的等價類的重寫組成.研究項重寫系統(tǒng)可能面臨的主要問題之一是對具有匯合或終止等基本性質(zhì)的重寫系統(tǒng)類的刻畫.終止的性質(zhì)保證了任意項在重寫法則之下都可以終止于一個規(guī)范型.此外,如果項重寫系統(tǒng)是匯合的,那么規(guī)范型是唯一的.因此,無論重寫法則使用的是哪一種序關(guān)系,一個既終止又匯合的項重寫系統(tǒng)保證了它具有唯一規(guī)范型的特性,參見文獻(xiàn)[15-18].這些論文對終止和匯合及其相關(guān)性質(zhì)進(jìn)行了全面研究.終止性和匯合性這兩個性質(zhì)是極其重要的,本文將基于自由幺半群上的重寫系統(tǒng)對它們進(jìn)行廣泛研究.

項重寫也可以在Herbrand-G¨odel可計算性中找到.后來,項重寫系統(tǒng)的概念以其目前的形式被提出,并被用于實現(xiàn)規(guī)格分析、可計算性理論、字問題和定理證明.隨著里程碑論文中完成方法的出現(xiàn),文獻(xiàn)[18]為這個領(lǐng)域帶來了新的生機(jī).Knuth-Bendix程序操作重寫系統(tǒng),這個十分關(guān)鍵.這些系統(tǒng)被用來簡化字問題,試圖解決特定的有限群或有限呈現(xiàn)的幺半群的字問題.

終止與匯合問題在重寫系統(tǒng)的研究中起著不可或缺的作用.研究這些問題的一種方法是將注意力限制在簡單類型的代數(shù)結(jié)構(gòu)上,如幺半群,這已經(jīng)被非常成功地運用在文獻(xiàn)[19-21]中.另外,要強(qiáng)調(diào)一下,在過去的幾十年里,人們對半群和幺半群上的重寫系統(tǒng)進(jìn)行了深入的研究.文獻(xiàn)[22]研究了中國幺半群,證明了中國幺半群具有收斂的重寫系統(tǒng).對于自由幺半群A*中的每一個元素,都有一個算法來求其規(guī)范型.因此,中國幺半群的字問題是可解的.給定一個具有有限多左右理想的正則半群,如果每個極大子群都能用一個有限的完備重寫系統(tǒng)表示,那么該半群也是如此.這一結(jié)果由Gray和文獻(xiàn)[23]證明.文獻(xiàn)[24]利用楊表計數(shù)的組合性質(zhì),構(gòu)造了相應(yīng)的Plactic幺半群的有限完備重寫系統(tǒng).

本文沿著這條線,利用重寫系統(tǒng)的理論,研究了收斂重寫系統(tǒng)與自由幺半群的商截面的關(guān)系.作為應(yīng)用,分別得到了由三個元素生成的Plactic幺半群和中國幺半群的商截面.

論文的結(jié)構(gòu)安排如下.在第2章中,首先回顧了項重寫系統(tǒng)的一些基本定義和符號.接下來,研究了專門用于自由幺半群上的項重寫系統(tǒng)的新結(jié)果,得到了所使用的重寫系統(tǒng)的一些基本結(jié)果.特別地,應(yīng)用重寫系統(tǒng)的方法給出了一個統(tǒng)一的方法來研究收斂重寫系統(tǒng)和自由幺半群商截面之間的關(guān)系.第3章分別研究了由3個元素生成的Plactic幺半群(定理4.1)和中國幺半群(定理4.2)的商截面.

2 自由幺半群上的項重寫系統(tǒng)

本節(jié)首先介紹一些基于自由幺半群的項重寫系統(tǒng)的一些符號和結(jié)果[25-26].現(xiàn)在,把項重寫系統(tǒng)與集合A生成的自由幺半群A*上的一個二元關(guān)系聯(lián)系起來.

定義2.1[27]設(shè)A是集合,A+是字母表A中所有限非空字a1a2···am的集合.A+上的一個二元運算定義為

其中m,n∈N.關(guān)于這個二元運算,稱A+為A上的自由半群.若在A+中添加單位1(作為空字),則得到A上的自由幺半群,記為A*.

定義2.2設(shè)A是集合,S?A*×A*,≤是A*上的線性序.

(a)定義

稱系統(tǒng)(A*,ΠS)為與S有關(guān)的A*上的項重寫系統(tǒng).稱ΠS中的元素(u,v)為ΠS的一個重寫法則,記為u→v.

(b)稱f∈A*一步重寫到g∈A*,記為或者更詳細(xì)地若存在a,b∈A*和u→v∈S,使得f=aub且g=avb.

(c)稱f∈A*關(guān)于ΠS n步(n≥1)重寫到g∈A*,記為若存在f0,f1,···,fn∈A*,使得fi/=fi+1,i=0,···,n-1且

若存在g∈V,n≥1,使得則稱f∈V為可約的.否則稱f為不可約的或者在規(guī)范型中.

(d)記二元關(guān)系的自反傳遞閉包關(guān)系→ΠS(作為A*上的一個二元關(guān)系)為若則稱f關(guān)于ΠS重寫為g,并稱f是g的前任.記P(g)為g的所有前任的全部集合.因此g∈P(g).

(e)稱f和g是匯合的,記為若存在h∈A*,使得則

定義2.3設(shè)A是集合,S?A*×A*,≤是A*上的線性序.稱項重寫系統(tǒng)(A*,ΠS)是

(c)收斂或者完備的,如果它既是終止的又是匯合的.

關(guān)于重寫系統(tǒng)的一個眾所周知的結(jié)果是Newman′s引理[25].

引理2.1(Newman)終止項重寫系統(tǒng)是匯合的當(dāng)且僅當(dāng)它是局部匯合的.

這里需要文獻(xiàn)[28]中的以下定義和引理.

定義2.4[28]稱A*上線性序≤為

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

(b)良構(gòu)造的,如果不存在無限形式的鏈x0＞x1＞x2＞···,其中x0,x1,···∈A*.在這種情況下,稱≤為可容許的.

容許良序在重寫系統(tǒng)中起著重要作用,見下面引理.

引理2.2[28]設(shè)A是集合,S?A*×A*,≤是A*上的線性序.則下面兩條陳述是等價的:

(a)項重寫系統(tǒng)(A*,ΠS)是終止的;

(b)線性序≤是A*上的一個容許良序.

3 收斂的項重寫系統(tǒng)和截面

本節(jié)將刻畫自由幺半群A*上的收斂項重寫系統(tǒng)和A*的商截面之間的關(guān)系.

對于一個二元關(guān)系S?A*×A*,記〈S〉為S生成的同余.每個同余〈S〉都有一個相應(yīng)的商結(jié)構(gòu)A*/〈S〉,它是由該關(guān)系的同余類組成.

定義3.1設(shè)A是集合,S?A*×A*.若對于〈S〉的每一個同余類A,恰好存在唯一的元素w∈W使得w∈A,則稱A*的子集W為A*/〈S〉的截面.

定義3.2設(shè)U是半群且U1是具有鄰接單位的半群.設(shè)S是U上二元關(guān)系.若c,d∈U使得c=xay,且d=xby,對于U1中一些元素x,y,其中(a,b)或(b,a)也屬于S,則可以說c通過一個基本S-傳遞與d相連.

這里需要下列引理.

引理3.1[27]設(shè)S是半群U上的關(guān)系,并且a,b∈U.則(a,b)∈〈S〉當(dāng)且僅當(dāng)a=b或者存在一個基本S-傳遞序列a=z1-z2-···-zn=b,n≥1,連結(jié)a到b,其中〈S〉是由S生成的同余.

引理3.2設(shè)A是集合,S?A*×A*,≤是A*上線性序.如果那么(f,g)∈〈S〉.

證明如果f=g,那么顯然(f,g)∈〈S〉.假設(shè).設(shè)n≥1是使得的最小數(shù).對n作歸納來證明這一結(jié)果.對于n=1的歸納起點,根據(jù)定義2.2,存在a,b∈A*和(u,v)∈ΠS使得f=aub且g=avb,因此(f,g)∈〈S〉.對于n＞1的歸納步驟,令

根據(jù)歸納假設(shè),可得(f,h)∈〈S〉和(h,g)∈〈S〉,利用同余的傳遞性,可得(f,g)∈〈S〉.

設(shè)≤是A*上的線性序.對于由A*上的二元關(guān)系S生成的同余〈S〉,定義

對于公式(1)中給出的項重寫系統(tǒng),記:

它是由A*的在(A*,ΠS)的規(guī)范型中的元素構(gòu)造的集合.

引理3.3設(shè)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),則設(shè)w∈Pm(〈S〉)∩Irr(S).因為w∈Irr(S),w在規(guī)范型中.又因為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在規(guī)范型中,所以有

若

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

并且通過可得v＞w,再次與方程(3)中的w＞v矛盾.所以zi+1,即,當(dāng)i≤n-2,存在zi+2,使得或者對于前一種情況,通過對于后一種情況,因為是一個分叉,w在規(guī)范型中,則由(A*,ΠS)是匯合的可得繼續(xù)這個過程,最后可得到和v＞w,這與等式(3)中w＞v矛盾.

(b)假設(shè)有相反的情形(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設(shè)A是集合,S?A*×A*,≤是A*上容性良序.則

證明因為Pm(〈S〉),Irr(S)?A*,由此可見Pm(〈S〉)∪Irr(S)?A*.相反地,設(shè)u∈A*.由引理2.2可知(A*,ΠS)是終止的,于是u有一個規(guī)范型v∈Irr(S),使得若u=v,則u∈Irr(S)?Pm(〈S〉)∪Irr(S),得證.假設(shè)u/=v.由引理3.2,可得(u,v)∈〈S〉.因為≤是容許的,所以v＜u,因此

證畢.

引理3.5設(shè)A是集合,≤是A*上的容性良序.對于〈S〉的每一個同余類A,有

證明由引理2.2可得項重寫系統(tǒng)(A*,ΠS)是終止的.設(shè)b∈A.則存在a∈Irr(S)使得由引理3.2,有(b,a)∈〈S〉,從而a∈A.因此且因為由b∈P(a)可得

反之,對任意元素a∈A,由引理3.2可得P(a)?A,從而證畢.

引理3.6設(shè)A是集合,S?A*×A*,≤是A*上的容性良序.對于〈S〉的每一個同余類A,若(A*,ΠS)是匯合的,則|A∩Irr(S)|=1.

證明由引理3.5,可得|A∩Irr(S)|≥1.假設(shè)有相反的情況|A∩Irr(S)|≥2.令

且|I|≥2,會出現(xiàn)兩種情形.

情形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)=?矛盾.假設(shè)1≤?＜n.則

定理3.1設(shè)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))假設(shè)(A*,ΠS)是匯合的.根據(jù)引理3.6,Irr(S)得每一個同余類恰只有一個元素,所以Irr(S)是A*/〈S〉的截面.

((d)?(b))假設(shè)(A*,ΠS)是不匯合的.則存在一個分叉是不可匯合的.因為(A*,ΠS)是終止的,可以假設(shè)且有u1,v1∈Irr(S),u11,所以根據(jù)引理3.2,有(w,u1),(w,v1)∈〈S〉,所以(u1,v1)∈〈S〉.因此在同一個同余類中Irr(S)包含兩個元素u1和v1,這與Irr(S)是A*/〈S〉的截面矛盾.證畢.

4 應(yīng)用

在本節(jié)中,分別給出由三個元素生成的Plactic幺半群[10]和中國幺半群[22]的截面.

定義4.1設(shè)A={x1,x2,x3}.由A生成的Plactic幺半群是A*模去同余〈S〉的商,其中S是Knuth關(guān)系:

擴(kuò)展生成元的集合A:x1＜x2＜x3上的序,為A*裝配一個帶權(quán)字典序≤wl.文獻(xiàn)[10]表示與上述S相關(guān)的項重寫系統(tǒng)是不收斂的;但在增加三個額外的重寫法則后,它是收斂的.記:

關(guān)聯(lián)S的項重寫系統(tǒng)(A*,ΠS)是收斂的.

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

(a)Plactic幺半群上的項重寫系統(tǒng)(A*,ΠS)是收斂的.

(b)項重寫系統(tǒng)(A*,ΠS)的規(guī)范型的集合是

作為該引理的直接結(jié)果,有

定理4.1采用上述符號,規(guī)范型的集合Irr(S)是秩為3的Plactic幺半群的截面.

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

接下來,給出了中國幺半群的截面.

定義4.2設(shè)A={x1,···,xn}.A上的中國幺半群是自由幺半群A*模掉中國同余〈S〉的商,其中

使用A*上的加權(quán)字典序≤wl,它擴(kuò)展了生成元上的序:x1＜x2＜···＜xn.與上述S相關(guān)的項重寫系統(tǒng)是不收斂的;但在添加一個新的重寫法則[22]后,它是收斂的.記:

引理4.2[22]采用上面的符號,中國幺半群的項重寫系統(tǒng)(A*,ΠS)是收斂的.

作為一個直接的結(jié)果,有

定理4.2采用上述符號,規(guī)范型的集合:是中國幺半群的截面.

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