BRICS Basic Research in Computer Science

B R ICS R S -01-42 ´Es ik & K ui ch: R a tio na lly Addi tive Semi ri ng s

BRICS

Basic Research in Computer Science

Rationally Additive Semirings

Zolt´an ´ Esik Werner Kuich

BRICS Report Series RS-01-42

Copyright c 2001, Zolt´an ´ Esik & Werner Kuich.

BRICS, Department of Computer Science University of Aarhus. All rights reserved.

Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy.

See back inner page for a list of recent BRICS Report Series publications.

Copies may be obtained by contacting:

BRICS

Department of Computer Science University of Aarhus

Ny Munkegade, building 540 DK–8000 Aarhus C

Denmark

Telephone: +45 8942 3360 Telefax: +45 8942 3255 Internet: BRICS@brics.dk

BRICS publications are in general accessible through the World Wide Web and anonymous FTP through these URLs:

http://www.brics.dk ftp://ftp.brics.dk

This document in subdirectory RS/01/42/

Rationally Additive Semirings

Zolt´an ´Esik¹

(Department of Computer Science, The University of Szeged, ´Arp´ad t´er 2, H-6720 Szeged, Hungary.

Email: esik@inf.u-szeged.hu.) Werner Kuich²

( Institut f¨ur Algebra und Computermathematik, Technische Universit¨at Wien, Wiedner Hauptstraße 8–10, A-1040 Wien, Austria.

Email: kuich@tuwien.ac.at.)

Abstract: We define rationally additive semirings that are a generalization of (ω)- complete and (ω-)continuous semirings. We prove that every rationally additive semir- ing is an iteration semiring. Moreover, we characterize the semirings of rational power series with coefficients in N∞, the semiring of natural numbers equipped with a top element, as the free rationally additive semirings.

Key Words: semiring, complete semiring, iteration semiring, fixed point, power se- ries.

Category: F.4.3

1 Introduction

Rationally additive semirings arise in [Mohri 1998]. Rationally additive semiring possess enough infinite sums to solve any finite system of linear fixed point equa- tions. They are a common generalization of (ω)-complete and (ω-)continuous semirings [see Eilenberg 1974, Kuich 1987, Sakarovitch 1987, Kuich 1997] in which all (countable) sums exist. Two prime examples of rationally additive semirings are the semiring of rational (or regular) sets inA^∗, whereAis any set, and the semiringN_∞^rathhA^∗iiof rational power series overAwith coefficients inN_∞, the semiring of natural numbers with a top element∞.

In our main result, Theorem 10, we prove that every rationally additive semir- ing is an iteration semiring. This fact extends a result of [Hebisch 1990] by which every complete semiring is a Conway semiring. Iteration semirings appear implic- itly in [Conway 1971]. They were explicitly defined in [Bloom, ´Esik 1993a, 1993b].

Conway conjectured that a complete axiomatization of the equational theory of rational (regular) languages consists of the Conway semiring equations, defined below, together with the equation 1^∗= 1 and an equation associated with each finite group. Conway’s conjecture was confirmed in [Krob 1991], see also [ ´Esik 1999]. In [Bloom, ´Esik 1997], the authors conjectured that the valid equations of

1 Partially supported by BRICS, Aalborg, Denmark, grant no. T30511 from the Na- tional Foundation of Hungary for Scientific Research, grant no. A-4/1999 from the Austrian-Hungarian Bilateral Research and Development Fund, and by a grant from the Austrian-Hungarian Action Foundation.

2 Partially supported by grant no. A-4/1999 from the Austrian-Hungarian Bilateral Research and Development Fund and by a grant from the Austrian–Hungarian Ac- tion Foundations.

rational power series with coefficients in N_∞, the semiring of natural numbers equipped with a top element, can be axiomatized by the iteration semiring equa- tions and the equation 1^∗ = 1^∗∗. This conjecture is still open. In Theorem 15, we characterize the semirings of rational power series with coefficients inN_∞ as the free rationally additive semirings.

2 Conway semirings and iteration semirings

A^∗-semiringis a semiring [see Kuich, Salomaa 1986, Golan 1992]S = (S,+,·,0,1) equipped with a star operation ^∗ : S → S. A Conway semiring [Bloom, ´Esik 1993b] is a^∗-semiringS which satisfies thesum-starandproduct-starequations

(x+y)^∗= (x^∗y)^∗x^∗ (1)

(xy)^∗= 1 +x(yx)^∗y. (2)

Note that thefixed point equation

x^∗= 1 +xx^∗ (3)

holds in any Conway semiring. (Substitute 1 fory in (2).)

Suppose that S is a ^∗-semiring and n ≥ 0. We turn the matrix semiring S^n×n into a ^∗-semiring. LetM ∈S^n×n. When n= 0,M^∗ is the unique 0×0 matrix, and when M = [a], then M^∗ = [a^∗]. Suppose now that n >1. Write M =

a b c d

, whereais (n−1)×(n−1) anddis 1×1. We define

M^∗= α β

γ δ

(4) where

α= (a+bd^∗c)^∗ β=αbd^∗ γ=δca^∗ δ= (d+ca^∗b)^∗.

Theorem 1. [Conway 1971, Bloom, ´Esik 1993] IfS is a Conway semiring, then so is each matrix semiring S^n×n. Moreover, the above matrix formula (4) holds for each way of splitting M into four blocks M =

a b c d

such thata andd are square matrices.

Suppose thatGis a finite group of ordernwith elementsg₁, . . . , g_n. For each g_i, letx_idenote a variable associated withg_i. We defineM_G= [ (M_G)_ij], where (M_G)_ijis the variable associated with the group elementg⁻¹_i g_j, i.e., (M_G)_ij =x_k whereg_k =g⁻¹_i g_j. The matrixM_G^∗ is defined as in (4) above, so that each entry ofM_G^∗ is a term in the variablesx₁, . . . , x_n.

Thegroup-equation associated withG[see Conway 1971] is the equation e·M_G^∗ ·u= (x₁+. . .+x_n)^∗,

where eis the 1×nrow matrix whose first entry is 1 and whose other entries are 0, and whereuis the n×1 column matrix whose entries are all 1. (Under the Conway semiring equations (1) and (2), the particular orderg₁, . . . , g_nof the group elements is irrelevant.)

Aniteration semiring[see Bloom, ´Esik 1993, ´Esik 1999] is a Conway semiring satisfying all group-equations.

Proposition 2. [Bloom, ´Esik 1993b] Any Conway semiring S satisfying the functorial implication

AC=CB⇒A^∗C=CB^∗,

for all matricesA∈S^n×n, B∈S^m×mandC∈S^n×m, is an iteration semiring.

NotationFor each nonnegative integern, we denote the set {1, . . . , n} by [n]. Thus, [0] is another name for the empty set.

For any setΣ, we denote byΣ^∗the free monoid of all words overΣincluding the empty word. WhenS is semiring,ShhA^∗iidenotes the semiring of all power series overAwith coefficients inS. Moreover, we letShAidenote the collection of all finite sums of terms of the formsawiths∈S anda∈Σ.

3 Rationally additive semirings

A weak rationally additive semiring is a semiring S equipped with a partial summation P

i∈Is_i defined on countable families s_i ∈ S, i ∈I subject to the following conditions:

– Ax₁. Whens_i∈S fori∈F andF is finite, then P

i∈Fs_i is the sum of the s_ias defined in the semiringS.

– Ax₂. For eachs∈S, the geometric sumP_∞

n=0sⁿ exists.

– Ax₃. If P

i∈Is_i exists, then so doP

i∈Iss_i and P

i∈Is_is, for each s ∈ S, moreover,

s(X

i∈I

s_i) =X

i∈I

ss_i

(X

i∈I

s_i)s=X

i∈I

s_is.

– Ax₄. Suppose that the countable setIis the disjoint union of the setsI_j, j∈ J. Then for any familys_i ∈S,i∈I, ifr_j =P

i∈Ijs_i exists for each j∈J, and ifr=P

j∈Jr_j exists, thenP

i∈Is_ialso exists and equalsr.

A rationally additive semiring is a weak rationally additive semiring S that satisfies:

– Ax₅.Suppose that the countable setIis the disjoint union of the setsI_j, j∈ J. Then for any familys_i∈S,i∈I, ifs=P

i∈Is_i exists andr_j =P

i∈Ijs_i exist, for allj∈J, thenP

j∈Jr_j exists and equalss.

Proposition 3. Suppose that S is a weak rationally additive semiring.

– For any countable families s_i, i ∈ I and r_j, j ∈ J, if P

i∈Is_i = s and P

j∈Jr_j=rexist, then so doesP

(i,j)∈I×Js_ir_j. Moreover,P

(i,j)∈I×Js_ir_j= sr.

– For any countable familiess_i ∈S ands⁰_j ∈S withi∈I and j∈J, if there is a bijection π: I→ J with s_i =s⁰_iπ, for all i∈ I, then P

i∈Is_i exists iff P

j∈Js⁰_j does, in which case the two sums are equal.

– Any countable sumP

i∈Isexists. Moreover,P

i∈I0 = 0, i.e., any countable sum of0 with itself is0.

– For any countable familys_i, i∈I, ifP

j∈Js_j =r exists, whereJ is the set of alli∈I with s_i6= 0, thenP

i∈Is_i exists and equalsr.

Proof. The first claim follows fromAx₃andAx₄. For the second, suppose that P

i∈Is_i=sexists. LetJ_i ={iπ}, for each i∈I. Thus the sets J_i determine a partition ofJ. Each sum P

k∈Jis⁰_k =s⁰_iπ =s_i exists, moreover,P

i∈Is_i exists.

Thus, byAx₄, we have thatP

j∈Js⁰_jexists and equalsP

i∈Is_i. In the same way, it follows that if P

j∈Js⁰_j exists then P

i∈Is_i also exists. For the third claim, assume first that s = 1. If I is finite with n elements, then P

i∈Is = P

i∈I1 exists byAx₁, and equals the usualn-fold sum of 1 with itself. Assume now that I is infinite. Then P

i∈Is=P

i∈I1 =P_∞

i=01ⁱ exists byAx₂. Thus for any s, we have thatP

i∈Is=P

i∈I(s·1) =s(P

i∈I1) exists. Whensis 0, this sum is also 0. The last claim now follows fromAx₄.2

Remark. WhenS is rationally additive, the converse of the last fact also holds, so that using the same notation,P

j∈Js_j exists iffP

i∈Is_i exists.

Suppose that S and S⁰ are (weak) rationally additive semirings. A homo- morphism h: S → S⁰ is a semiring homomorphism that preserves all existing countable sums. Thus, if P

i∈Is_i exists, where s_i ∈ S for each i ∈ I, then so doesP

i∈Is_ihand (P

i∈Is_i)h=P

i∈Is_ih.

Example 1. A countably additive (orω-complete) semiring is a rationally addi- tive semiringS such thatP

i∈Is_i exists for all countable familiess_i∈S,i∈I.

For example, the power set semiring of a semiring is countably additive, where summation is defined by set union. An example of a rationally additive semiring which is not countably additive is the semiring of regular sets in A^∗, where A is any set. In this semiring only those sums (unions) exist that are regular lan- guages. An ω-continuous (or just continuous) semiring is a countably additive semiring which is naturally ordered and such thatP

i∈Is_i is the supremum of the finite sumsP

i∈Fs_i, for all finite subsetsF ⊆I. Since any countably addi- tive semiring is rationally additive, so is any ω-continuous semiring. For more on complete and continuous semirings, the reader is referred to [Eilenberg 1974, Kuich 1987, Sakarovitch 1987, Kuich 1997].

Example 2. A prime example of a countably additive semiring is the semiring N_∞ ={0,1, . . . ,∞} obtained by adding a top element to the natural numbers N equipped with the following summation. For all n_i ∈N_∞, i∈I, where I is countable, define P

i∈In_i =∞ ifn_i =∞for somei, or if n_i >0 for infinitely many numbers i. Otherwise let P

i∈In_i be the ordinary sum. Note that all countable sums exist inN_∞. Moreover, we havex· ∞=∞ ·x=∞for allx6= 0.

We call the above countably additive structure onN_∞ the standard countably additive structure.

Remark. The same semiringSmay sometimes be turned into a weak rationally additive semiring in several different ways. Suppose that we have a weak ra- tionally additive structure on S with summation denotedP

. Then there is a smallest weak rationally additive structure onS contained in P

. If we denote the summation operation of this structure byP₀

, we have thatP₀

i∈Is_iexists iff I is finite, or there is an elements∈S such that for some linear orderi₀, i₁, . . . of the set I, we have that s_in =sⁿ, for alln≥0, or there is a family s⁰_i,i∈I and an element s⁰ ∈ S such that either s_i =s⁰_is⁰ for all i or s_i =s⁰s⁰_i for all i, or there exist disjoint sets I_j, j ∈ J with I =∪j∈JI_j such thatr_j =P₀

i∈Ijs_j exists for eachj∈J andP₀

j∈Jr_j exists. In either case,P₀

i∈Is_i, when exists, is defined to be P

i∈Is_i. In the same way, each rationally additive structure onS contains a least rationally additive structure.

Remark. There exists a weak rationally additive semiring which is not rationally additive. For one example, take the (standard) countably additive semiringN_∞ defined above. It will be shown below in Corollary 14 that N_∞ has no other rationally additive structure properly included in the standard structure. On the other hand, consider the least weak rationally additive structure contained in it.

Let P₀

denote the corresponding summation. Then there is only a countable number of sets K ⊆ N such that P₀

k∈Kk exists. Hence this weak additive semiring structure is not the standard countably additive structure.

In any (weak) rationally additive semiring, we define

∗:S →S s7→X^∞

n=0

sⁿ.

It is clear that morphisms of (weak) rationally additive semirings preserve the

∗-operation.

Proposition 4. Any weak rationally additive semiringS is a Conway semiring.

Proof. Suppose thata, b∈Sand letaandbdenote distinct letters corresponding toaandb, respectively. Below we will use regular languages in (a+b)^∗ as index sets. For any word w∈(a+b)^∗, let wdenote the corresponding element in S.

Since (a+b)^∗=P_∞

n=0(a+b)ⁿ exists, it follows byAx₄ thatP

w∈(a+b)^∗walso exists, and (a+b)^∗ =P

w∈(a+b)^∗w. Let us partition (a+b)^∗ into the disjoint union of the sets L_k = (a^∗b)^ka^∗, k≥0. It follows by Ax₂ and Ax₃ that each

sumP

w∈Lkwexists, andP

w∈Lkw= (a^∗b)^ka^∗. Thus, again byAx₂ andAx₃, P_∞

k=0(a^∗b)^ka^∗= (a^∗b)^∗a^∗exists. Since for eachkwe haveP

w∈Lkw= (a^∗b)^ka^∗, it follows from Ax₄ that P

w∈Lw = (a^∗b)^∗a^∗. Hence (a+b)^∗ = P

w∈Lw = (a^∗b)^∗a^∗.

Also,P_∞

k=0a(ba)^kb=a(P_∞

k=0(ba)^k)b=a(ba)^∗bexists, hence byAx₄, (ab)^∗= P_∞

k=0(ab)^k = 1 +P_∞

k=0a(ba)^kb= 1 +a(ba)^∗b.2

Corollary 5. Thefixed point equation(3) holds in any weak rationally additive semiring.

Proposition 6. Any weak rationally additive semiring S satisfies 1^∗ = 1^∗∗, 1^∗1^∗= 1^∗ and 1^∗+ 1^∗= 1^∗.

Proof. Equation 1^∗+ 1^∗= 1^∗ follows fromAx₄. By Proposition 3, 1^∗1^∗= (

X∞ i=0

1)(

X∞ i=0

1) = X∞ i,j=0

1 = X∞ k=0

1 = 1^∗, and byAx₃,

1^∗1^∗= X∞ i=0

X∞ j=0

1.

Hence, (1^∗)ⁿ= 1^∗, for alln≥1. Moreover, 1^∗∗= 1 +

X∞ n=1

(1^∗)ⁿ= 1 + X∞ n=0

1^∗= 1 + X∞ n=0

X∞ m=0

1 = 1 + 1^∗= 1^∗, where the last step follows from the fixed point equation.2

Remark. In fact, the equations 1^∗1^∗= 1^∗and 1^∗+ 1^∗= 1^∗ hold in any Conway semiring satisfying 1^∗∗= 1^∗.

Suppose thatSis a weak rationally additive semiring. Then, as shown above, S is a Conway semiring. Thus, by Theorem 9, the semirings S^n×n, n ≥0 are also Conway semirings. Moreover, for each decomposition of a matrixA∈S^n×n in the formA=

a b c d

, whereaanddare square matrices, we have A^∗=

α β γ δ

(5) where

α= (a+bd^∗c)^∗ β=αbd^∗ γ=δca^∗ δ= (d+ca^∗b)^∗.

Suppose now that S is rationally additive. We turn S^n×n into a rationally ad- ditive semiring. Suppose that A_i ∈ S^n×n, i ∈ I where I is countable. We say

that P

i∈IA_i exists ifP

i∈I(A_i)_jk exists for all j, k ∈[n]. Moreover, we define (P

i∈IA_i)_jk = P

i∈I(A_i)_jk, for each j, k ∈ [n]. We define the summation on countable families of matrices inS^n×m, forn, m≥0 in the same way.

Proposition 7. Suppose that S is rationally additive. If A_i ∈ S^n×m, i ∈ I such that P

i∈IA_i exists, then for any B ∈S^m×p, P

i∈IA_iB exists and equals (P

i∈IA_i)B.

Proof. It suffices to prove the proposition forp= 1. We argue by induction on m. The case that m= 0 is trivial. Whenm= 1, the proposition holds byAx₃. Suppose now thatm >1. Then letm=m₁+m₂, wherem₁, m₂< m, and let us writeA_i= [a_ib_i],i∈I, andB =

x y

, wherea_iisn×m₁, etc. Leta=P

i∈Ia_i and b =P

i∈Ib_i, so that A =P

i∈IA_i = [a b]. By the induction assumption, bothP

i∈Ia_ixandP

i∈Ib_iyexist, moreover,P

i∈Ia_ix=axandP

i∈Ib_iy=by.

SinceAx₅holds inS, it follows thatP

i∈I(a_ix+b_iy) exists and equalsax+by.

Thus,P

i∈IA_iB= (P

i∈IA_i)B exists. Note that only a weak form ofAx₅ was used: the case when each setI_j is finite.2

In the same way, we have:

Proposition 8. Suppose that S is rationally additive. If A_i ∈ S^n×m, i ∈ I such that P

i∈IA_i exists, then for any B ∈S^p×n, P

i∈IBA_i exists and equals B(P

i∈IA_i).

Theorem 9. When S is rationally additive, so is S^n×n, for anyn≥0. More- over, for the star operation defined in (5), we have

A^∗= X∞ k=0

A^k.

Proof. Our claims are clear forn= 0,1. We proceed by induction onn. Assume thatn >1. It is clear thatAx₁, Ax₄andAx₅hold inS^n×n. The fact thatAx₃ holds was shown above.

Suppose now thatA = a b

c d

∈S^n×n, where a, b, c, dare submatrices ofA such thataanddare square matrices of size smaller thann. We want to show that P_∞

k=0A^k =A^∗, i.e., thatP_∞

k=0A^k exists and X∞

k=0

A^k = α β

γ δ

whereα,β,γandδwere given as above. We will only show that the submatrix ofP_∞

k=0A^k at the left upper corner exists and equalsα.

Consider the regular languageL = (a+bd^∗c)^∗. Then Lis the union of the disjoint setsL^k₁,k≥0, whereL₁=a+bd^∗c. By the induction assumption,

a+bd^∗c=a+b(

X∞ j=0

d^j)c=a+ X∞ j=0

bd^jc=a+ X

w∈bd^∗c

w= X

w∈L1

w.

Hence, by Proposition 7 and Proposition 8, (a+bd^∗c)²= (X

w∈L1

w)(X

w∈L1

w) = X

u,v∈L1

uv= X

w∈L²₁

w,

since each word in L²₁ has a unique factorization as a product of two words in L₁. In the same way, it follows that

(a+bd^∗c)^k= X

w∈L^k₁

w,

for allk≥0. Thus, by the induction assumption, (a+bd^∗c)^∗=

X∞ k=0

(a+bd^∗c)^k = X∞ k=0

X

w∈Lk

w= X

w∈L

w.

In particular,P

w∈Lwexists. Now let us write A^k = a_k b_k

c_k d_k

,k≥0. To com- plete the proof, we need show thatP_∞

k=0a_k exists and equalsP

w∈Lw. But for each k, a_k =P

w∈L,|w|=kw. Thus, since Ax₅ holds by the induction assump- tion,P_∞

k=0a_k exists and equalsP

w∈Lw. (Again note that only the weak form ofAx₅ when the setsI_j are finite has been used.)2

Theorem 10. Any rationally additive semiringS is an iteration semiring sat- isfying 1^∗= 1^∗∗.

Proof. We have already proved that any rationally additive semiringSis a Con- way semiring and satisfies 1^∗ = 1^∗∗. The fact that the group-equations hold follows from the functorial implication, see Proposition 2, which can be estab- lished as follows. Suppose that A ∈ S^n×n, B ∈ S^m×m and C ∈ S^n×m with AC=CB. ThenA^kC=CB^k, for allk≥0. Thus, by Propositions 7 and 8,

A^∗C= ( X∞ k=0

A^k)C= X∞ k=0

A^kC= X∞ k=0

CB^k =C(

X∞ k=0

B^k) =CB^∗. 2

Assume that S is a rationally additive semiring and A is a set. We turn the power series semiring ShhA^∗ii into a rationally additive semiring. For any countable family r_i ∈ShhA^∗ii, i∈ I, we say that P

i∈Ir_i is defined if the sum P

i∈I(r_i, u) is defined for allu∈A^∗. Moreover, in this case, we let (P

i∈Ir_i, u) = P

i∈I(r_i, u).

Proposition 11. Suppose that S is a rationally additive semiring and A is a set. Then ShhA^∗iiis also a rationally additive semiring.

Proof. We only show that Ax₂ andAx₃ hold in ShhA^∗ii. So suppose thatr ∈ ShhA^∗ii. We clearly have that

X∞ n=0

(rⁿ, ) = X∞ n=0

(r, )ⁿ = (r, )^∗. Suppose now that u 6= . Then (rⁿ, u) = P

u1...un=u(r, u₁). . .(r, u_n). Thus, by Ax₅, P_∞

n=0(rⁿ, u) exists if the sum P

u1...un=u, n≥0(r, u₁). . .(r, u_n) does.

But this latter sum indeed exists. This can be seen as follows. For each fixed u₁, . . . , u_k 6= withu₁. . . u_k=u,

X

m0,...,mk≥0

(r, )^m0(r, u₁). . .(r, u_k)(r, )^mk = (r, )^∗(r, u₁). . .(r, u_k)(r, )^∗ exists. SinceP

u1...un=u(r, u₁). . .(r, u_n) is just a finite sum of sums of this form, it follows byAx₄that this sum also exists. Again, only a weak form ofAx₅has been used.2

The following fact is clear.

Proposition 12. Suppose that S is a (weak) rationally additive semiring and S⁰ is a subsemiring ofS which is closed under^∗. Say that P

i∈Is_i exists inS⁰, wheres_i ∈S⁰ for all i∈I, if P

i∈Is_i exists inS and belongs toS⁰, and in that case, let the sum in S⁰ be the same as in S. Then S⁰ is also a (weak) rationally additive semiring.

WhenS is a^∗-semiring and B ⊆S, theB-rational elementsof S are those contained in the^∗-semiring generated byB. Thus theB-rational elements form a^∗-semiring denotedRatS(B), or justRat(B). LetS be rationally additive and letAbe a set. Then, as shown above,ShhA^∗iiis also rationally additive and each a ∈ A and s ∈ S can be conveniently identified with a series in ShhA^∗ii. We denoteS^rathhA^∗ii=Rat_ShhA^∗_ii(A∪S).

The countably additive semiringN_∞ was defined above.

Proposition 13. Suppose that S is rationally additive. Then there is a unique morphism N_∞→S.

Proof. Clearly, any morphismh: N_∞ →S is forced to map each integer n to the n-fold sum of 1 with itself and ∞ to 1^∗. The fact that this function is in turn a morphism will follow by Remark 3 once we prove that for any countably infinite familyn_i, i∈I of nonzero elements ofN_∞, the sumP

i∈In_ihexists in S and equals 1^∗. But this follows by Proposition 3.2

Corollary 14. There exits no rationally additive semiring structure on N_∞ properly included in the standard structure.

Theorem 15. For each setA,N_∞^rathhA^∗iiis freely generated byAin the class of rationally additive semirings.

Proof. We need to show that if S is a rationally additive semiring and his a functionA→S, thenhhas a unique extension to a morphismh^]:N_∞^rathhA^∗ii → S of rationally additive semirings. Suppose thatr∈N_∞^rathhA^∗ii. We are forced to define

rh^]= X

(r,u)6=0

(r, u)uh, (6)

where for any word u = a₁. . . a_n ∈ A^∗ of length n, we define uh = (a₁h)· . . .·(a_nh). Note that the coefficient (r, u) of uh in (6) is taken in S. This is meaningful, since to each integer nthere corresponds in S the n-fold sum of 1 with itself, and to∞the element 1^∗. See Proposition 13.

In a natural way, we may extendhto a function N_∞hAi →S, and then to a function (N_∞hAi)^n×n →S^n×n, for eachn≥0. For each n∈N_∞ anda∈A we define (na)h=n(ah). For a finite sumP

i∈Fn_ia_i, we define (P

i∈Fn_ia_i)h= P

i∈Fn_i(a_ih).

We must show that the sum on the right-hand side of (6) exists. Since r is rational, by (a generalization of) Sch¨utzenberger’s theorem [see Bloom, ´Esik 1993b], there exists α ∈ N_∞^1×n, M ∈ N_∞hAi^n×n and β ∈ N_∞^n×1 with r = αM^∗β. Now, by Theorem 9 and Propositions 7 and 8, we have thatα(M h)^∗β= P_∞

k=0α(M h)^kβ exists. But for eachk, α(M h)^kβ= X

|u|=k,(r,u)6=0

(r, u)uh.

Thus, byAx₄, the right-hand side of (6) exists and equalsα(M h)^∗β.

Note that for any finite setB⊆Asuch thatu∈B^∗holds for all wordsu∈A^∗ with (r, u)6= 0, i.e., such thatsupp(r)⊆B^∗, we have thatrh^]=P

u∈B^∗(r, u)uh.

We use this fact in our proof thath^] preserves all existing sums. Suppose that r_i ∈ N_∞^rathhA^∗ii, i ∈ I such that P

i∈Ir_i exists in N_∞^rathhA^∗ii, so that P

i∈Ir_i is rational. Since r = P

i∈Ir_i is rational, there is a finite set B ⊆ A with supp(r)⊆B^∗. Clearly then,supp(ri)⊆B^∗ for alli∈I. ByAx₄ andAx₅, the fact thatP

i∈Ir_ih^]exists and equalsrh^]will follow if we can show that the sum P

u∈B^∗, i∈I(r_i, u)uhexists and equalsrh^]. This in turn will hold if for each fixed

u∈B^∗, X

i∈I

(r_i, u)uh= (X

i∈I

(r_i, u))uh

exists and is equal to (r, u)uh. But by Proposition 13, the sumP

i∈I(r_i, u) exists in S, and equals (r, u).2

Corollary 16. There is no rationally additive structure on N_∞^rathhA^∗ii properly contained in the rationally additive structure inherited from the countably addi- tive structure onN_∞hhA^∗ii.

References

1. [Bloom, ´Esik 1993a] Bloom, S. L., ´Esik, Z.: “Matrix and Matricial Iteration Theo- ries”;J. Computer and System Sciences, 46, (1993), 381–408.

2. [Bloom, ´Esik 1993b] Bloom, S. L., ´Esik, Z.,: “Iteration Theories”; Springer-Verlag (1993).

3. [Bloom, ´Esik 1997] Bloom, S. L., ´Esik, Z.: “The Equational Logic of Fixed Points”;

Theoretical Computer Science, 179, (1997), 1–60.

4. [Conway 1971] Conway, J: “Regular Algebra and Finite Machines”; Chapman and Hall (1971).

5. [Eilenberg 1974] Eilenberg, S.: “Automata, Languages and Machines”, Vol. A; Aca- demic Press (1974).

6. [´Esik 1999] ´Esik, Z.: “Group Axioms for Iteration”; Information and Computation, 148 (1999), 131–180.

7. [´Esik, Kuich 2001] ´Esik, Z., Kuich, W.: “Inductive^∗-Semirings”; to appear.

8. [Golan 1992] Golan, J. S.: “The Theory of Semirings, With Applications in Mathe- matics and Computer Science”; Longman Scientific (1992).

9. [Hebish 1990] Hebisch, U.: “The Kleene Theorem in Countably Complete Semir- ings”; Bayreuth. Math. Schr., 31, (1990), 55–66.

10. [Krob 1991] Krob, D.: “Complete Systems of B-Rational Identities”; Theoretical Computer Science, 89, (1991), 207–343.

11. [Kuich 1987] W. Kuich: “The Kleene and the Parikh Theorem in Complete Semir- ings”; Proc. ICALP 87, LNCS 267, Springer-Verlag (1987), 212–225.

12. [Kuich 1997] Kuich, W.: “Semirings and Formal Power Series”, Handbook of For- mal Languages, Vol. 1, Springer-Verlag (1997), 609–677.

13. [Kuich, Salomaa 1986] Kuich, W., and Salomaa, A.: Semirings, Automata, Lan- guages; Springer-Verlag (1986).

14. [Mohri 1998] Mohri, M.: “General Algebraic Frameworks for Short-Distance Prob- lems”; Technical Report, AT & T Labs-Research (1998).

15. [Sakarovitch 1987] Sakarovitch, J.: “Kleene’s Theorem Revisited”; Trends, Tech- niques, and Problems in Theoretical Computer Science, LNCS 281, Springer-Verlag (1987), 39–50.

Recent BRICS Report Series Publications

RS-01-42 Zolt´an ´ Esik and Werner Kuich. Rationally Additive Semirings.

November 2001. 11 pp.

RS-01-41 Ivan B. Damg˚ard and Jesper Buus Nielsen. Perfect Hiding and Perfect Binding Universally Composable Commitment Schemes with Constant Expansion Factor. October 2001. 43 pp.

RS-01-40 Daniel Damian and Olivier Danvy. CPS Transformation of Flow Information, Part II: Administrative Reductions. October 2001. 9 pp.

RS-01-39 Olivier Danvy and Mayer Goldberg. There and Back Again.

October 2001. 14 pp.

RS-01-38 Zolt´an ´ Esik. Free De Morgan Bisemigroups and Bisemilattices.

October 2001. 13 pp.

RS-01-37 Ronald Cramer and Victor Shoup. Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption. October 2001. 34 pp.

RS-01-36 Gerth Stølting Brodal, Rolf Fagerberg, and Riko Jacob. Cache Oblivious Search Trees via Binary Trees of Small Height. Octo- ber 2001.

RS-01-35 Mayer Goldberg. A General Schema for Constructing One- Point Bases in the Lambda Calculus. September 2001. 6 pp.

RS-01-34 Flemming Friche Rodler and Rasmus Pagh. Fast Random Ac- cess to Wavelet Compressed Volumetric Data Using Hashing.

August 2001. 31 pp.

RS-01-33 Rasmus Pagh and Flemming Friche Rodler. Lossy Dictionar- ies. August 2001. 14 pp. Short version appears in Meyer auf der Heide, editor, 9th Annual European Symposiumon on Al- gorithms, ESA ’01 Proceedings, LNCS 2161, 2001, pages 300–

311.

RS-01-32 Rasmus Pagh and Flemming Friche Rodler. Cuckoo Hash-

ing. August 2001. 21 pp. Short version appears in Meyer auf

der Heide, editor, 9th Annual European Symposiumon on Al-

gorithms, ESA ’01 Proceedings, LNCS 2161, 2001, pages 121–