沈曉芹,田徑,豐丕虎

(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仍為弱歸納的一個(gè)充分條件.即若S2×2是λ-半環(huán),則S2×2是弱歸*-半環(huán).應(yīng)用這一結(jié)果可以證明S上的二元仿射映射存在最小的聯(lián)立不動(dòng)點(diǎn),部分回答了相關(guān)文獻(xiàn)中的公開問題.

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

1 引言及基本概念

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

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

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

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

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

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

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

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

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

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

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

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

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

稱偏序*-半環(huán)S為歸納*-半環(huán)[6],如果對(duì)任意的a,b∈S有:稱滿足積星恒等式與和星恒等式的半環(huán)為Conway半環(huán).稱偏序*-半環(huán)S為弱歸納*-半環(huán),如果它滿足不動(dòng)點(diǎn)方程、和星恒等式以及弱不動(dòng)點(diǎ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).對(duì)任意的a,b∈S,如果線性映射fa,b有最小不動(dòng)點(diǎn)(前不動(dòng)點(diǎn)),則稱S為λ-半環(huán)(μ-半環(huán)).

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

2 矩陣

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

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

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

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

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

證明已經(jīng)證明了(i)?(ii)成立.另外,由引理2.1知(iii)?(ii)成立.又因?yàn)?-λ-半環(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滿足不動(dòng)點(diǎn)方程(3)與和星恒等式(7).如果S2×2是*-λ-半環(huán),那么對(duì)任意的A,B∈S2×2,A*B是方程AX+B=X的最小不動(dòng)點(diǎn).這就說明S2×2滿足弱不動(dòng)點(diǎn)歸納法則(8)式.故,S2×2是弱歸納*-半環(huán).

3 聯(lián)立不動(dòng)點(diǎn)

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

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

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

[1]馮鋒,劉曉燕.弱歸納*-半環(huán)上仿射映射的聯(lián)立不動(dòng)點(diǎn)[J].數(shù)學(xué)進(jìn)展,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.

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

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

2010 MSC:16Y60