沈曉芹,田徑,豐丕虎

(1.西安理工大學(xué)理學(xué)院,陜西西安 710054；2.西北大學(xué)數(shù)學(xué)系,陜西西安 710069)

關(guān)于交換的弱歸*-半環(huán)的研究

沈曉芹1,田徑1,豐丕虎2

(1.西安理工大學(xué)理學(xué)院,陜西西安 710054；2.西北大學(xué)數(shù)學(xué)系,陜西西安 710069)

研究了交換的弱歸納*-半環(huán)S上的二階方陣半環(huán)S2×2.給出S2×2仍為弱歸納的一個充分條件.即若S2×2是λ-半環(huán),則S2×2是弱歸*-半環(huán).應(yīng)用這一結(jié)果可以證明S上的二元仿射映射存在最小的聯(lián)立不動點,部分回答了相關(guān)文獻中的公開問題.

λ-半環(huán)；*-半環(huán)；矩陣半環(huán)；最小聯(lián)立不動點

1 引言及基本概念

半環(huán)是由德國數(shù)學(xué)家Dedekind在研究交換環(huán)的理想時提出的一種代數(shù)結(jié)構(gòu).自上個世紀六十年代開始,半環(huán)理論在Kleene,Eilenberg,Salomma等學(xué)者的推動下成為理論計算機科學(xué)中最重要的代數(shù)理論之一.

設(shè)S為非空集合.一個(2,2,0,0)型代數(shù)(S,+,·,0,1)是半環(huán),記為S,如果

(i)(S,+)是可換的含幺半群,其中0是恒等元；

(ii)(S,·)是幺半群,其中1是恒等元且1/= 0；

(iii)對任意的a,b,c∈S有a·(b+c)=a·b+a·c,(b+c)·a=b·a+c·a；

(iv)對任意的a∈S有a·0=0·a=0.

以下對任意的a,b∈S,將a·b記為ab.

另一方面,不動點理論和與不動點的計算相關(guān)的課題在計算機科學(xué)的各個學(xué)科中都扮演著重要的角色.關(guān)于不動點的基本理論參見文獻[2-4].

設(shè)P是偏序集,f是P上的映射.若有P中的元素x滿足f(x)=x,則稱x為f的不動點.若f的所有不動點組成的集合存在最小元,則記該最小元為λf；若P中的元素x滿足f(x)≤x,則稱x為f的前不動點.若f的所有前不動點組成的集合存在最小元,則記該最小元為μf.

設(shè)S是半環(huán).若≤是S上的偏序關(guān)系,使S上的加法和乘法運算是單調(diào)的,則稱S是偏序半環(huán)；若半環(huán)S上帶有一個一元運算*:S→S(稱為*運算),則稱S是*-半環(huán)；若半環(huán)S既是偏序半環(huán)又是*-半環(huán),則稱它為偏序*-半環(huán).

設(shè)S是半環(huán).對任意a,b∈S,稱映射fa,b:x→ax+b為S上的仿射變換.對任意a1,a2,b1∈S,稱二元映射(x,y)→a1x+a2y+b1為S上的二元仿射變換.由于偏序半環(huán)上的加法和乘法是單調(diào)的,容易發(fā)現(xiàn)偏序半環(huán)上的仿射變換也是單調(diào)的.

隨著計算機科學(xué)的發(fā)展,半環(huán)上連續(xù)映射的不動點受到人們的關(guān)注.著名學(xué)者Golan[5]指出:半環(huán)理論最重要的應(yīng)用,主要體現(xiàn)在半環(huán)上仿射變換的不動點的相關(guān)性質(zhì).如,半環(huán)上仿射變換的不動點的存在性,唯一性及最小性.

2004年ˊEsik和Kuich[6]在Conway半環(huán)[7]的基礎(chǔ)上將一些具有不動點性質(zhì)的方程作為公理,并利用這些公理定義了歸納*-半環(huán),進而推廣了Kleene定理.2007年文獻[8]同樣利用方程的公理化方法定義了*-μ-半環(huán)和*-λ-半環(huán).并借助它們解決了ˊEsik等人提出的一個公開問題,即:弱歸納*-半環(huán)上的形式冪級數(shù)半環(huán)仍是弱歸納的.

稱偏序*-半環(huán)S為歸納*-半環(huán)[6],如果對任意的a,b∈S有:稱滿足積星恒等式與和星恒等式的半環(huán)為Conway半環(huán).稱偏序*-半環(huán)S為弱歸納*-半環(huán),如果它滿足不動點方程、和星恒等式以及弱不動點歸納法則:

引理1.1[6]弱歸納*-半環(huán)是Conway半環(huán).

引理1.2[7]若S是Conway半環(huán),則Sn×n也是Conway半環(huán).

定義1.1[8]設(shè)S是偏序半環(huán).對任意的a,b∈S,如果線性映射fa,b有最小不動點(前不動點),則稱S為λ-半環(huán)(μ-半環(huán)).

文獻[6]還提出下面的公開問題:若S是弱歸*-半環(huán),Sn×n是否仍為弱歸納*-半環(huán)?本文針對S是交換的弱歸納*-半環(huán)的情形,給出S2×2是弱歸納*-半環(huán)的一個充分條件,即:若S2×2是λ-半環(huán),則它是弱歸納*-半環(huán).利用這一結(jié)果研究了(Δ)的聯(lián)立不動點.證明如果S2×2上的仿射變換存在最小不動點,那么S2×2有最小的聯(lián)立不動點并且它就是文獻[1]中構(gòu)造的聯(lián)立不動點.

2 矩陣

由S是弱歸納*-半環(huán),有

定理2.1若S是交換的弱歸納*-半環(huán),則以下命題等價:

(i)S2×2是λ-半環(huán)；

(ii)S2×2是*-λ-半環(huán)；

(iii)S2×2是弱歸納*-半環(huán).

證明已經(jīng)證明了(i)?(ii)成立.另外,由引理2.1知(iii)?(ii)成立.又因為*-λ-半環(huán)一定是λ-半環(huán),所以(iii)?(i)成立.現(xiàn)在證明(ii)?(iii)成立.

設(shè)S是弱歸納*-半環(huán).由引理1.1知,S是Conway半環(huán).再由引理1.2知S2×2也是Conway半環(huán).那么S2×2滿足不動點方程(3)與和星恒等式(7).如果S2×2是*-λ-半環(huán),那么對任意的A,B∈S2×2,A*B是方程AX+B=X的最小不動點.這就說明S2×2滿足弱不動點歸納法則(8)式.故,S2×2是弱歸納*-半環(huán).

3 聯(lián)立不動點

是f和g的聯(lián)立不動點.進一步,由定理2.1知道它是f和g的最小聯(lián)立不動點.即有

推論3.1設(shè)S是交換的弱歸納*-半環(huán).如果S上的二元映射存在聯(lián)立不動點,那么它們一定存在最小的聯(lián)立不動點.

因此,部分地回答了文獻[1]中提出的問題.

[1]馮鋒,劉曉燕.弱歸納*-半環(huán)上仿射映射的聯(lián)立不動點[J].數(shù)學(xué)進展,2008,37(3):283-290.

[2]Tarski A.A lattice-theoretical fixpoint theorem and its applications[J].Pacific Journal of Mathematics, 1955,5:285-309．

[3]Davis A.A characterization of complete lattices[J].Pacific Journal of Mathematics,1955,5:311-319.

[4]Abian A,Brown A.A theorem on partially ordered sets with applications to fixed point theorems[J].Canadian J.of Math.,1961,13:173-174.

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

[7]Conway J.Regular Algebra and Finite Machines[M].London:Chapman and Hall,1971.

[8]Feng F,Zhao X,Jun Y.B semirings and semirings[J].Theoretical Computer Science,2005,347:423-431.

On commutative weak inductive*-semirings

Shen Xiaoqin1,Tian Jing1,Feng Pihu2

(1.School of Scince,Xi′an University of technology,Xi′an710054,China； 2.Department of Mathematics,Northwest University,Xi′an710069,China)

The semiring S2×2of 2×2 matrices over a commutative weak inductive*-semiring S is studied.It is shown that if 2×2 is a λ-semiring then it is a weak inductive*-semiring again.Then the least simultaneous fixed points of two binary affine maps over S are given.

λ-semiring,*-semiring,matrices semirings,least simultaneous fixed points

O153.3

A

1008-5513(2012)04-0540-06

2011-02-10.

國家自然科學(xué)基金(11101330)；陜西省自然科學(xué)基金青年基金(2011JQ1007).

沈曉芹(1981-),博士,講師,研究方向：代數(shù)及密碼理論.

2010 MSC:16Y60