田徑，孫曉青，李江華

(西安理工大學(xué) 理學(xué)院，陜西 西安 710048)

1 引言與預(yù)備知識(shí)

近年來，隨著理論計(jì)算機(jī)科學(xué)的發(fā)展和實(shí)際應(yīng)用的需要，關(guān)于強(qiáng)雙幺半群的研究受到理論計(jì)算機(jī)學(xué)者和代數(shù)學(xué)者的重視。作為一類比環(huán)[1]和半環(huán)更為一般的代數(shù)系統(tǒng)，強(qiáng)雙幺半群不必滿足乘法對(duì)加法的分配律，因此也被稱為偽半環(huán)。

設(shè)(S,+,·,0,1)是一個(gè)(2,2,0,0)-型代數(shù)。如果(S,+,0)和(S,·,1)都是幺半群，則稱(S,+,·,0,1)為雙幺半群。進(jìn)一步，若對(duì)任意a,b∈S都有a+b=b+a和a·0=0·a=0·0=0成立，則稱(S,+,·,0,1)為強(qiáng)雙幺半群[4]。稱強(qiáng)雙幺半群S是加法冪等的，如果對(duì)任意的a∈S，總有a+a=a成立。此外，稱一個(gè)強(qiáng)雙幺半群S是右[左]分配的，如果對(duì)任意的a,b,c∈S,總有等式(a+b)·c=a·c+b·c[c·(a+b)=c·a+c·b]成立。通常的半環(huán)就是滿足左、右分配律的強(qiáng)雙幺半群。

例1：

1) 代數(shù)(N∞,+,min,0,∞)是強(qiáng)雙幺半群[5],其中N∞=N∪{∞}，+和min是自然數(shù)集N上通常的加法和取極小元運(yùn)算并滿足對(duì)任意的a∈N∞，有：

a+∞=∞+a=∞

min{a,∞}=min{∞,a}=a

若n為正整數(shù),則有：

min{n,n+n}=n≠n+n=min{n,n}+min{n,n}

故分配律不成立。

2) 代數(shù)([0,1],⊕,·,0,1)是強(qiáng)雙幺半群[8],其中·是通常實(shí)數(shù)的乘法,利用通常實(shí)數(shù)的加法和減法定義二元運(yùn)算⊕定義為:

3) 設(shè)(C,+,0)是一個(gè)交換的幺半群。CC是集合C到其自身映射的全體。對(duì)任意的f,g∈CC,令f+g仍為定義在C上的映射使得(f+g)(c)=f(c)+g(c)對(duì)所有c∈C成立。再定義恒等映射和常元映射I1和I0,為:

那么代數(shù)(CC,+,°,I0,I1)是只滿足右分配律的強(qiáng)雙幺半群,這里對(duì)任意的f,g∈CC和c∈C,有(f°g)(c)=f(g(c))。

顯然，由全體加法冪等的右分配的強(qiáng)雙幺半群形成的代數(shù)類是一個(gè)簇[9]，記為RS。本文研究RS的兩個(gè)子簇LRS和URS分別滿足附加恒等式y(tǒng)+xy≈y和y+xy≈xy。第2節(jié)利用后綴碼的代數(shù)性質(zhì)，構(gòu)造兩個(gè)(2,2,0,0)-型代數(shù)并證明它們分別屬于LRS和URS。進(jìn)一步將在第3節(jié)證明這兩個(gè)代數(shù)分別是LRS和URS的自由對(duì)象。

2 后綴碼

設(shè)X為非空字符集，稱為字母表。稱X中有限多個(gè)字符形成的字符串為X上的字。特別地稱不含任何字符的字為空字，記為ε。稱由若干字形成的集合(有限或無限)為形式語言(或語言)。進(jìn)一步，記X*為X上字的全體。對(duì)任意的x,y∈X*,記xy為字x和y的并置,即：xy=x1x2…xny1y2…ym,其中，x=x1x2…xn,y=y1y2…ym,n,m為正整數(shù)，則xy∈X*。易見, 并置是X*上的二元運(yùn)算。在并置運(yùn)算的意義下，X*成為一個(gè)幺半群，稱為由X生成的自由幺半群 。并稱X+=X*{ε}為由X生成的自由半群[10]。

定義X*上的二元關(guān)系≤，為:

容易驗(yàn)證，≤是X*上的偏序關(guān)系。設(shè)A?X+是一個(gè)非空語言。若A中任意兩個(gè)不同的字在偏序關(guān)系≤下都無法比較，則稱A為X上的后綴碼[11]。記X上有限后綴碼的全體為S(X)。顯然,A為后綴碼當(dāng)且僅當(dāng)下列蘊(yùn)含式成立：

例2 設(shè)X={a,b}并且A={a,ba,bb}，B={aa,bb,ab}。A不是后綴碼B是后綴碼。

文獻(xiàn)[10]詳細(xì)闡述了后綴碼的組合性質(zhì)與代數(shù)性質(zhì)。并證明如果A和B都是后綴碼，則A°B也是后綴碼，這里°是通常語言的乘法運(yùn)算，定義為：

(?X,Y?X*)X°Y={xy∈X*|x∈X,y∈Y}.

由于運(yùn)算°是結(jié)合的，所以(S(X),°)是半群。

給定非空集A?X+。令L(A)[U(A)]為A在偏序關(guān)系≤下極小元[極大元]的全體，即：

L(A)={x∈A|(?y∈A)y≤x?y=x}

U(A)={x∈A|(?y∈A)x≤y?y=x}

由后綴碼的定義容易證明性質(zhì)1。

性質(zhì) 1：設(shè)非空集A?X+，那么以下兩個(gè)結(jié)論成立：

①L(A)和U(A)都是后綴碼；

②A為后綴碼當(dāng)且僅當(dāng)L(A)=U(A)=A。

根據(jù)性質(zhì)1，在S(X)上定義兩個(gè)二元運(yùn)算+和⊕，即：

這樣就得到了兩個(gè)(2,2)-型代數(shù)(S(X),+,°)和(S(X),⊕,°)。

進(jìn)一步，有：

假設(shè)xy≤uv,其中，x∈A∪B,y∈C。則存在z∈X*，使得uv=zxy。令v=vn…v2v1,y=ym…y2y1,其中vi,yj∈X，i=1,2,…,n,j=1,2,…,m。顯然,當(dāng)n=m時(shí)有v=y。若n

uv=zxy?v=y?u=zx(因?yàn)閡v=uyz)

?x≤u

?u=x(因?yàn)閡,x∈A∪B且u是A∪B的極小元)

?uv=xy

所以,w=uv∈A°C+B°C。因此,(A+B)°C?A°C+B°C。

例3給出一個(gè)在自然語言處理中被用到的右分配的強(qiáng)雙幺半群,參見文獻(xiàn)[12]。

例3：設(shè)X為字母表。令∧為X*上的二元運(yùn)算。對(duì)任意的u,v∈X*,u∧v是u和v的最長(zhǎng)公共后綴。在X*中額外添加一個(gè)字∞，要求w∧∞=∞∧w=w,w·∞=∞·w=∞對(duì)一切w∈X*∪{∞}都成立,其中·為字的并置。

例4：設(shè)X={a,b}且A={a},B={ba},C={ab}。易見,A,B,C∈S(X)。由于A+B=L(A∪B)={a}且A⊕B=U(A∪B)={ba},則有：

C°(A+B)={ab}°{a}={aba}

C°(A⊕B)={ab}°{ba}={abba}

又因?yàn)椋篊°A+C°B={aba}+{abba}={aba,abba}

C°A⊕C°B={aba}⊕{abba}={aba,abba}

所以,C°(A+B)≠C°A+C°B且C°(A⊕B)≠C°A⊕C°B。

3 自由對(duì)象

引理1：設(shè)X為非空集合, (K,+,·,0,1)∈LRS且α:X→K為映射。令乘法幺半群同態(tài)θ:X*→K是α的擴(kuò)張。那么對(duì)任意的非空有限集A?X*，總有∑w∈Aθ(w)=∑w∈L(A)θ(w)。

證明：設(shè)u,v∈A，若u≤v,則v=xu,其中x∈X*。因?yàn)槌朔ㄍ瑧B(tài)θ是α的擴(kuò)張,所以θ(ε)=1且θ(v)=θ(xu)=θ(x)θ(u)。由(K,+,·,0,1)∈LRS,知(K,+,·,0,1)滿足恒等式x+xy≈x。故有：

θ(u)+θ(v)=θ(u)+θ(u)θ(x)=θ(u)

所以有：∑w∈Aθ(w)=∑w∈A{v}θ(w)。進(jìn)一步根據(jù)A的有限性得到 ：

∑w∈Aθ(w)=∑w∈L(A)θ(w)

那么, 對(duì)任意的x∈X,有β(ι(x))=β({x})=θ(x)=α(x).因此,圖1是交換的。

圖1 α的擴(kuò)張

下面證明β是同態(tài)映射。

β(A)+β(B) =∑w∈Aθ(w)+∑w∈Bθ(w)

=∑w∈A∪Bθ(w)=∑w∈L(A∪B)θ(w)

=∑w∈A+Bθ(w)=β(A+B),

β(A)·β(B)=(∑w∈Aθ(w))·(∑w∈Bθ(w))

=∑u∈A,v∈Bθ(u)·θ(v)

=∑w∈A°Bθ(w)=β(A°B)

這就證明了定理1和定理2

參考文獻(xiàn)：

[1]孫曉青，田徑，李江華.具有擬穩(wěn)定秩的環(huán)[J].西安理工大學(xué)學(xué)報(bào), 2013,29(2): 188-191.

Sun Xiaoqing, Tian Jing, Li Jianghua.Rings with quasi-stable range conditions[J].Journal of Xi’an University of Technology,2013,29 (2):188-191.

[2]Bloom S, ésik Z.Free shuffle algebras in language varieties[J].Theoretical Computer Science, 1996, 163:55-98.

[3]Chatterjee K, Doyen L, Henzinger T.Quantitative languages[J].Lecture Notes in Computer Science, 2008, 5213:385-400.

[5]Droste M, Stüber T, Vogler H.Weighted finite automata over strong bimonoids[J].Information Sciences, 2010, 180:156-166.

[6]Chatterjee K, Doyen L, Henzinger T.Alternating weighted automata[J].Lecture Notes in Computer Science, 2009, 5699:3-13.

[7]Chatterjee K, Doyen L, Henzinger T.Expressiveness and closure properties for quantitative languages: 24th LICS 2009[M].Los Angeles: IEEE Computer Society Press, 2009, 199-208.

[8]Klir G J, Yuan B.Fuzzy sets and fuzzy logic, theory and application[M].New Jersey: Prentice-Hall PTR, 1995.

[9]Burris S, Sankappanavar H P.A course in universal algebra[M].New York：Dover Publications, Incorporated, 2012.

[10]Shyr H J.Lecture notes: free monoids and languages[M].3rd Edition.Taiwan：Hon Min Book Company, 2001.

[11]Ito M, Jürgensen H,Shyr H J.Outfix and infix codes and related classes of languages[J].Journal of Computer and System Sciences, 1991, 43:484-508.

[12]Mohri M.Minimization algorithms for sequential transducers[J].Theoretical Computer Science, 2000, 234:177-201.