關于交換的弱歸*-半環的研究

沈曉芹,田徑,豐丕虎

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

關于交換的弱歸*-半環的研究

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

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

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

λ-半環；*-半環；矩陣半環；最小聯立不動點

1 引言及基本概念

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

設S為非空集合.一個(2,2,0,0)型代數(S,+,·,0,1)是半環,記為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.

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

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

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

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

隨著計算機科學的發展,半環上連續映射的不動點受到人們的關注.著名學者Golan[5]指出:半環理論最重要的應用,主要體現在半環上仿射變換的不動點的相關性質.如,半環上仿射變換的不動點的存在性,唯一性及最小性.

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

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

引理1.1[6]弱歸納*-半環是Conway半環.

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

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

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

2 矩陣

由S是弱歸納*-半環,有

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

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

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

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

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

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

3 聯立不動點

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

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

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

[1]馮鋒,劉曉燕.弱歸納*-半環上仿射映射的聯立不動點[J].數學進展,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.

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

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

2010 MSC:16Y60