林沐辰,朱志成,張毅

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

(a)定義

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

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

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

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

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

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

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

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

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

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

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

定義2.4[28]稱(chēng)A*上線(xiàn)性序≤為

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

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

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

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

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

(b)線(xiàn)性序≤是A*上的一個(gè)容許良序.

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

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

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

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

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

這里需要下列引理.

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

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

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

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

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

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

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

引理3.3設(shè)A是集合,S?A*×A*,≤是A*上的線(xiàn)性序.

(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).因?yàn)閣∈Irr(S),w在規(guī)范型中.又因?yàn)閣∈Pm(〈S〉),則存在v∈A*使得

由引理3.1,對(duì)于任意n≥1和zi∈A*,1≤i≤n,存在一個(gè)基本S-傳遞序列w=z1-z2-···-zn=v,連接w到v.則對(duì)任意的1≤i≤n-1,

由等式(1),因?yàn)閣=z1在規(guī)范型中,所以有

若

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

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

(b)假設(shè)有相反的情形(A*,ΠS)是不匯合的.則存在分叉是不可匯合的.因?yàn)?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*上容性良序.則

證明因?yàn)镻m(〈S〉),Irr(S)?A*,由此可見(jiàn)Pm(〈S〉)∪Irr(S)?A*.相反地,設(shè)u∈A*.由引理2.2可知(A*,ΠS)是終止的,于是u有一個(gè)規(guī)范型v∈Irr(S),使得若u=v,則u∈Irr(S)?Pm(〈S〉)∪Irr(S),得證.假設(shè)u/=v.由引理3.2,可得(u,v)∈〈S〉.因?yàn)椤苁侨菰S的,所以v＜u,因此

證畢.

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

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

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

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

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

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

情形1:對(duì)于一些i,j∈I且在這種情況下,存在為一個(gè)分叉.因?yàn)閍i,aj∈Irr(S)且aiaj,所以ai和aj不可匯合,這與(A*,ΠS)是匯合的相矛盾.

情形2:對(duì)任意i,j∈I且因?yàn)?ai,aj)∈〈S〉,針對(duì)引理3.1,存在一個(gè)基本S-傳遞序列ai=z1-z2-···-zn=aj,連接ai到aj,n≥1,zk∈A*,1≤k≤n.類(lèi)似于引理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*上的容性良序.則以下陳述是等價(jià)的.

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

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

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

證明因?yàn)椤苁茿*上的容性良序,由引理2.2知(A*,ΠS)是終止的.所以(a)和(b)是等價(jià)的.由引理3.3,引理3.4可知(b)和(c)的等價(jià)性.

((b)?(d))假設(shè)(A*,ΠS)是匯合的.根據(jù)引理3.6,Irr(S)得每一個(gè)同余類(lèi)恰只有一個(gè)元素,所以Irr(S)是A*/〈S〉的截面.

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

4 應(yīng)用

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

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

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

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

引理4.1[10]用上面的符號(hào),

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

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

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

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

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

接下來(lái),給出了中國(guó)幺半群的截面.

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

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

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

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

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

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