BRICS RS-01-42 Ésik & Kuich: Rationally Additive Semirings BRICS

Basic Research in Computer Science

Rationally Additive Semirings

Zoltán Ésik Werner Kuich BRICS Report Series RS-01-42 ISSN 0909-0878 November 2001 Copyright \begin{matrix}c \\ ◯ \end{matrix} 2001, Zoltán Ésik & 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án Ésik^{1}

(Department of Computer Science, The University of Szeged, Árpád tér 2, H-6720 Szeged, Hungary. Email: esik@inf.u-szeged.hu.)

Werner Kuich^{2}

( Institut für Algebra und Computermathematik, Technische Universität 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 semiring 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 series. 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 equations. 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 in A^{∗}, where A is any set, and the semiring N_{∞}^{rat}⟨⟨A^{∗}⟩⟩ of rational power series over A with coefficients in N_{∞}, the semiring of natural numbers with a top element ∞.

In our main result, Theorem 10, we prove that every rationally additive semiring is an iteration semiring. This fact extends a result of [Hebisch 1990] by which every complete semiring is a Conway semiring. Iteration semirings appear implicitly in [Conway 1971]. They were explicitly defined in [Bloom, Ésik 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 [Ésik 1999]. In [Bloom, Ésik 1997], the authors conjectured that the valid equations of

1 Partially supported by BRICS, Aalborg, Denmark, grant no. T30511 from the National 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 Action 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 equations and the equation 1^{∗} = 1^{∗∗}. This conjecture is still open. In Theorem 15, we characterize the semirings of rational power series with coefficients in N_{∞} as the free rationally additive semirings.

2 Conway semirings and iteration semirings

A^{∗}-semiring is a semiring [see Kuich, Salomaa 1986, Golan 1992] S = (S, +, ·, 0, 1) equipped with a star operation ^{∗} : S → S. A Conway semiring [Bloom, Ésik 1993b] is a ^{∗}-semiring S which satisfies the sum-star and product-star equations

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

Note that the fixed point equation

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

holds in any Conway semiring. (Substitute 1 for y in (2).)

Suppose that S is a ^{∗}-semiring and n ≥ 0. We turn the matrix semiring S^{n×n} into a ^{∗}-semiring. Let M ∈ 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 = [ \begin{matrix}a & b \\ c & d \end{matrix} ], where a is (n − 1) × (n − 1) and d is 1 × 1. We define

M^{∗} = [ \begin{matrix}α & β \\ γ & δ \end{matrix} ]  (4)

where

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

Theorem 1. [Conway 1971, Bloom, Ésik 1993] If S 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 = [ \begin{matrix}a & b \\ c & d \end{matrix} ] such that a and d are

square matrices.

Suppose that G is a finite group of order n with elements g_{1}, …, g_{n}. For each g_{i}, let x_{i} denote a variable associated with g_{i}. We define M_{G} = [ (M_{G})_{ij}], where (M_{G})_{ij} is the variable associated with the group element g_{i}^{−1}g_{j}, i.e., (M_{G})_{ij} = x_{k} where g_{k} = g_{i}^{−1}g_{j}. The matrix M_{G}^{∗} is defined as in (4) above, so that each entry of M_{G}^{∗} is a term in the variables x_{1}, …, x_{n}.

The group-equation associated with G [see Conway 1971] is the equation

e · M_{G}^{∗} · u = (x_{1} + … + x_{n})^{∗},

where e is the 1 × n row matrix whose first entry is 1 and whose other entries are 0, and where u is the n × 1 column matrix whose entries are all 1. (Under the Conway semiring equations (1) and (2), the particular order g_{1}, …, g_{n} of the group elements is irrelevant.)

An iteration semiring [see Bloom, Ésik 1993, Ésik 1999] is a Conway semiring satisfying all group-equations.

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

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

for all matrices A ∈ S^{n×n}, B ∈ S^{m×m} and C ∈ S^{n×m}, is an iteration semiring.

Notation For each nonnegative integer n, 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 ϵ. When S is semiring, S⟨⟨A^{∗}⟩⟩ denotes the semiring of all power series over A with coefficients in S. Moreover, we let S⟨A⟩ denote the collection of all finite sums of terms of the form sa with s ∈ S and a ∈ Σ.

3 Rationally additive semirings

A weak rationally additive semiring is a semiring S equipped with a partial summation ∑_{i∈I} s_{i} defined on countable families s_{i} ∈ S, i ∈ I subject to the following conditions:

– Ax_{1}. When s_{i} ∈ S for i ∈ F and F is finite, then ∑_{i∈F} s_{i} is the sum of the s_{i} as defined in the semiring S.

– Ax_{2}. For each s ∈ S, the geometric sum ∑_{n=0}^{∞} s^{n} exists.

– Ax_{3}. If ∑_{i∈I} s_{i} exists, then so do ∑_{i∈I} ss_{i} and ∑_{i∈I} s_{i}s, for each s ∈ S, moreover,

s(∑_{i∈I} s_{i}) = ∑_{i∈I} ss_{i}

(∑_{i∈I} s_{i})s = ∑_{i∈I} s_{i}s.

– Ax_{4}. Suppose that the countable set I is the disjoint union of the sets I_{j}, j ∈ J. Then for any family s_{i} ∈ S, i ∈ I, if r_{j} = ∑_{i∈I_{j}} s_{i} exists for each j ∈ J, and if r = ∑_{j∈J} r_{j} exists, then ∑_{i∈I} s_{i} also exists and equals r.

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

– Ax_{5}. Suppose that the countable set I is the disjoint union of the sets I_{j}, j ∈ J. Then for any family s_{i} ∈ S, i ∈ I, if s = ∑_{i∈I} s_{i} exists and r_{j} = ∑_{i∈I_{j}} s_{i} exist, for all j ∈ J, then ∑_{j∈J} r_{j} exists and equals s.

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 ∑_{i∈I} s_{i} = s and ∑_{j∈J} r_{j} = r exist, then so does ∑_{(i,j)∈I×J} s_{i}r_{j}. Moreover, ∑_{(i,j)∈I×J} s_{i}r_{j} = sr.

– For any countable families s_{i} ∈ S and s′_{j} ∈ S with i ∈ I and j ∈ J, if there is a bijection π : I → J with s_{i} = s′_{iπ}, for all i ∈ I, then ∑_{i∈I} s_{i} exists iff ∑_{j∈J} s′_{j} does, in which case the two sums are equal.

– Any countable sum ∑_{i∈I} s exists. Moreover, ∑_{i∈I} 0 = 0, i.e., any countable sum of 0 with itself is 0.

– For any countable family s_{i}, i ∈ I, if ∑_{j∈J} s_{j} = r exists, where J is the set of all i ∈ I with s_{i} ≠ 0, then ∑_{i∈I} s_{i} exists and equals r.

Proof. The first claim follows from Ax_{3} and Ax_{4}. For the second, suppose that ∑_{i∈I} s_{i} = s exists. Let J_{i} = {iπ}, for each i ∈ I. Thus the sets J_{i} determine a partition of J. Each sum ∑_{k∈J_{i}} s′_{k} = s′_{iπ} = s_{i} exists, moreover, ∑_{i∈I} s_{i} exists. Thus, by Ax_{4}, we have that ∑_{j∈J} s′_{j} exists and equals ∑_{i∈I} s_{i}. In the same way, it follows that if ∑_{j∈J} s′_{j} exists then ∑_{i∈I} s_{i} also exists. For the third claim, assume first that s = 1. If I is finite with n elements, then ∑_{i∈I} s = ∑_{i∈I} 1 exists by Ax_{1}, and equals the usual n-fold sum of 1 with itself. Assume now that I is infinite. Then ∑_{i∈I} s = ∑_{i∈I} 1 = ∑_{i=0}^{∞} 1^{i} exists by Ax_{2}. Thus for any s, we have that ∑_{i∈I} s = ∑_{i∈I}(s · 1) = s(∑_{i∈I} 1) exists. When s is 0, this sum is also 0. The last claim now follows from Ax_{4}. □

Remark. When S is rationally additive, the converse of the last fact also holds, so that using the same notation, ∑_{j∈J} s_{j} exists iff ∑_{i∈I} s_{i} exists.

Suppose that S and S′ are (weak) rationally additive semirings. A homomorphism h : S → S′ is a semiring homomorphism that preserves all existing countable sums. Thus, if ∑_{i∈I} s_{i} exists, where s_{i} ∈ S for each i ∈ I, then so does ∑_{i∈I} s_{i}h and (∑_{i∈I} s_{i})h = ∑_{i∈I} s_{i}h.

Example 1. A countably additive (or ω-complete) semiring is a rationally additive semiring S such that ∑_{i∈I} s_{i} exists for all countable families s_{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 languages. An ω-continuous (or just continuous) semiring is a countably additive semiring which is naturally ordered and such that ∑_{i∈I} s_{i} is the supremum of the finite sums ∑_{i∈F} s_{i}, for all finite subsets F ⊆ I. Since any countably additive 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 ∑_{i∈I} n_{i} = ∞ if n_{i} = ∞ for some i, or if n_{i} > 0 for infinitely many numbers i. Otherwise let ∑_{i∈I} n_{i} be the ordinary sum. Note that all countable sums exist in N_{∞}. Moreover, we have x · ∞ = ∞ · x = ∞ for all x ≠ 0. We call the above countably additive structure on N_{∞} the standard countably additive structure.

Remark. The same semiring S may sometimes be turned into a weak rationally additive semiring in several different ways. Suppose that we have a weak rationally additive structure on S with summation denoted ∑. Then there is a smallest weak rationally additive structure on S contained in ∑. If we denote the summation operation of this structure by ∑′, we have that ∑′_{i∈I} s_{i} exists iff I is finite, or there is an element s ∈ S such that for some linear order i_{0}, i_{1}, … of the set I, we have that s_{i_{n}} = s^{n}, for all n ≥ 0, or there is a family s′_{i}, i ∈ I and an element s′ ∈ S such that either s_{i} = s′_{i}s′ for all i or s_{i} = s′s′_{i} for all i, or there exist disjoint sets I_{j}, j ∈ J with I = ∪_{j∈J}I_{j} such that r_{j} = ∑′_{i∈I_{j}} s_{j} exists for each j ∈ J and ∑′_{j∈J} r_{j} exists. In either case, ∑′_{i∈I} s_{i}, when exists, is defined to be ∑_{i∈I} s_{i}. In the same way, each rationally additive structure on S 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 semiring N_{∞} 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 ∑′ denote the corresponding summation. Then there is only a countable number of sets K ⊆ N such that ∑′_{k∈K} k exists. Hence this weak additive semiring structure is not the standard countably additive structure.

In any (weak) rationally additive semiring, we define

∗ : S → S
s ↦ ∑_{n=0}^{∞} s^{n}.

It is clear that morphisms of (weak) rationally additive semirings preserve the ∗-operation.

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

Proof. Suppose that a, b ∈ S and let \overline{a} and \overline{b} denote distinct letters corresponding to a and b, respectively. Below we will use regular languages in (\overline{a} + \overline{b})^{∗} as index sets. For any word \overline{w} ∈ (\overline{a} + \overline{b})^{∗}, let w denote the corresponding element in S. Since (a + b)^{∗} = ∑_{n=0}^{∞}(a + b)^{n} exists, it follows by Ax_{4} that ∑_{\overline{w}∈(\overline{a}+\overline{b})^{∗}} w also exists, and (a + b)^{∗} = ∑_{\overline{w}∈(\overline{a}+\overline{b})^{∗}} w. Let us partition (\overline{a} + \overline{b})^{∗} into the disjoint union of the sets L_{k} = (\overline{a}^{∗}\overline{b})^{k}\overline{a}^{∗}, k ≥ 0. It follows by Ax_{2} and Ax_{3} that each sum ∑_{\overline{w}∈L_{k}} w exists, and ∑_{\overline{w}∈L_{k}} w = (a^{∗}b)^{k}a^{∗}. Thus, again by Ax_{2} and Ax_{3}, ∑_{k=0}^{∞}(a^{∗}b)^{k}a^{∗} = (a^{∗}b)^{∗}a^{∗} exists. Since for each k we have ∑_{\overline{w}∈L_{k}} w = (a^{∗}b)^{k}a^{∗}, it follows from Ax_{4} that ∑_{\overline{w}∈L} w = (a^{∗}b)^{∗}a^{∗}. Hence (a + b)^{∗} = ∑_{\overline{w}∈L} w = (a^{∗}b)^{∗}a^{∗}.

Also, ∑_{k=0}^{∞} a(ba)^{k}b = a(∑_{k=0}^{∞}(ba)^{k})b = a(ba)^{∗}b exists, hence by Ax_{4}, (ab)^{∗} = ∑_{k=0}^{∞}(ab)^{k} = 1 + ∑_{k=0}^{∞} a(ba)^{k}b = 1 + a(ba)^{∗}b. □

Corollary 5. The fixed 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 from Ax_{4}. By Proposition 3,

1^{∗}1^{∗} = (∑_{i=0}^{∞} 1)(∑_{i=0}^{∞} 1) = ∑_{i,j=0}^{∞} 1 = ∑_{k=0}^{∞} 1 = 1^{∗},

and by Ax_{3},

1^{∗}1^{∗} = ∑_{i=0}^{∞} ∑_{j=0}^{∞} 1.

Hence, (1^{∗})^{n} = 1^{∗}, for all n ≥ 1. Moreover,

1^{∗∗} = 1 + ∑_{n=1}^{∞}(1^{∗})^{n} = 1 + ∑_{n=0}^{∞} 1^{∗} = 1 + ∑_{n=0}^{∞} ∑_{m=0}^{∞} 1 = 1 + 1^{∗} = 1^{∗},

where the last step follows from the fixed point equation. □

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

Suppose that S is 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 matrix A ∈ S^{n×n}

in the form A = [ \begin{matrix}a & b \\ c & d \end{matrix} ], where a and d are square matrices, we have

A^{∗} = [ \begin{matrix}α & β \\ γ & δ \end{matrix} ]  (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 additive semiring. Suppose that A_{i} ∈ S^{n×n}, i ∈ I where I is countable. We say that ∑_{i∈I} A_{i} exists if ∑_{i∈I}(A_{i})_{jk} exists for all j, k ∈ [n]. Moreover, we define (∑_{i∈I} A_{i})_{jk} = ∑_{i∈I}(A_{i})_{jk}, for each j, k ∈ [n]. We define the summation on countable families of matrices in S^{n×m}, for n, m ≥ 0 in the same way.

Proposition 7. Suppose that S is rationally additive. If A_{i} ∈ S^{n×m}, i ∈ I such that ∑_{i∈I} A_{i} exists, then for any B ∈ S^{m×p}, ∑_{i∈I} A_{i}B exists and equals (∑_{i∈I} A_{i})B.

Proof. It suffices to prove the proposition for p = 1. We argue by induction on m. The case that m = 0 is trivial. When m = 1, the proposition holds by Ax_{3}. Suppose now that m > 1. Then let m = m_{1} + m_{2}, where m_{1}, m_{2} < m, and let us

write A_{i} = [ a_{i} b_{i}], i ∈ I, and B = [ \begin{matrix}x \\ y \end{matrix} ], where a_{i} is n × m_{1}, etc. Let a = ∑_{i∈I} a_{i}

and b = ∑_{i∈I} b_{i}, so that A = ∑_{i∈I} A_{i} = [ a b]. By the induction assumption, both ∑_{i∈I} a_{i}x and ∑_{i∈I} b_{i}y exist, moreover, ∑_{i∈I} a_{i}x = ax and ∑_{i∈I} b_{i}y = by. Since Ax_{5} holds in S, it follows that ∑_{i∈I}(a_{i}x + b_{i}y) exists and equals ax + by. Thus, ∑_{i∈I} A_{i}B = (∑_{i∈I} A_{i})B exists. Note that only a weak form of Ax_{5} was used: the case when each set I_{j} is finite. □

In the same way, we have:

Proposition 8. Suppose that S is rationally additive. If A_{i} ∈ S^{n×m}, i ∈ I such that ∑_{i∈I} A_{i} exists, then for any B ∈ S^{p×n}, ∑_{i∈I} BA_{i} exists and equals B(∑_{i∈I} A_{i}).

Theorem 9. When S is rationally additive, so is S^{n×n}, for any n ≥ 0. Moreover, for the star operation defined in (5), we have

A^{∗} = ∑_{k=0}^{∞} A^{k}.

Proof. Our claims are clear for n = 0, 1. We proceed by induction on n. Assume that n > 1. It is clear that Ax_{1}, Ax_{4} and Ax_{5} hold in S^{n×n}. The fact that Ax_{3} holds was shown above.

Suppose now that A = [ \begin{matrix}a & b \\ c & d \end{matrix} ] ∈ S^{n×n}, where a, b, c, d are submatrices of A

such that a and d are square matrices of size smaller than n. We want to show that ∑_{k=0}^{∞} A^{k} = A^{∗}, i.e., that ∑_{k=0}^{∞} A^{k} exists and

∑_{k=0}^{∞} A^{k} = [ \begin{matrix}α & β \\ γ & δ \end{matrix} ]

where α, β, γ and δ were given as above. We will only show that the submatrix of ∑_{k=0}^{∞} A^{k} at the left upper corner exists and equals α.

Consider the regular language L = (\overline{a} + \overline{b}\overline{d}^{∗}\overline{c})^{∗}. Then L is the union of the disjoint sets L_{1}^{k}, k ≥ 0, where L_{1} = \overline{a} + \overline{b}\overline{d}^{∗}\overline{c}. By the induction assumption,

a + bd^{∗}c = a + b(∑_{j=0}^{∞} d^{j})c = a + ∑_{j=0}^{∞} bd^{j}c = a + ∑_{\overline{w}∈\overline{b}\overline{d}^{∗}\overline{c}} w = ∑_{\overline{w}∈L_{1}} w.

Hence, by Proposition 7 and Proposition 8,

(a + bd^{∗}c)^{2} = ( ∑_{\overline{w}∈L_{1}} w)( ∑_{\overline{w}∈L_{1}} w) = ∑_{\overline{u},\overline{v}∈L_{1}} uv = ∑_{\overline{w}∈L_{1}^{2}} w,

since each word in L_{1}^{2} has a unique factorization as a product of two words in L_{1}. In the same way, it follows that

(a + bd^{∗}c)^{k} = ∑_{\overline{w}∈L_{1}^{k}} w,

for all k ≥ 0. Thus, by the induction assumption,

(a + bd^{∗}c)^{∗} = ∑_{k=0}^{∞}(a + bd^{∗}c)^{k} = ∑_{k=0}^{∞} ∑_{\overline{w}∈L_{k}} w = ∑_{\overline{w}∈L} w.

In particular, ∑_{\overline{w}∈L} w exists. Now let us write A^{k} = [ \begin{matrix}a_{k} & b_{k} \\ c_{k} & d_{k} \end{matrix} ], k ≥ 0. To com-

plete the proof, we need show that ∑_{k=0}^{∞} a_{k} exists and equals ∑_{\overline{w}∈L} w. But for each k, a_{k} = ∑_{\overline{w}∈L, |\overline{w}|=k} w. Thus, since Ax_{5} holds by the induction assumption, ∑_{k=0}^{∞} a_{k} exists and equals ∑_{\overline{w}∈L} w. (Again note that only the weak form of Ax_{5} when the sets I_{j} are finite has been used.) □

Theorem 10. Any rationally additive semiring S is an iteration semiring satisfying 1^{∗} = 1^{∗∗}.

Proof. We have already proved that any rationally additive semiring S is a Conway semiring and satisfies 1^{∗} = 1^{∗∗}. The fact that the group-equations hold follows from the functorial implication, see Proposition 2, which can be established as follows. Suppose that A ∈ S^{n×n}, B ∈ S^{m×m} and C ∈ S^{n×m} with AC = CB. Then A^{k}C = CB^{k}, for all k ≥ 0. Thus, by Propositions 7 and 8,

A^{∗}C = (∑_{k=0}^{∞} A^{k})C = ∑_{k=0}^{∞} A^{k}C = ∑_{k=0}^{∞} CB^{k} = C(∑_{k=0}^{∞} B^{k}) = CB^{∗}.

□

Assume that S is a rationally additive semiring and A is a set. We turn the power series semiring S⟨⟨A^{∗}⟩⟩ into a rationally additive semiring. For any countable family r_{i} ∈ S⟨⟨A^{∗}⟩⟩, i ∈ I, we say that ∑_{i∈I} r_{i} is defined if the sum ∑_{i∈I}(r_{i}, u) is defined for all u ∈ A^{∗}. Moreover, in this case, we let (∑_{i∈I} r_{i}, u) = ∑_{i∈I}(r_{i}, u).

Proposition 11. Suppose that S is a rationally additive semiring and A is a set. Then S⟨⟨A^{∗}⟩⟩ is also a rationally additive semiring.

Proof. We only show that Ax_{2} and Ax_{3} hold in S⟨⟨A^{∗}⟩⟩. So suppose that r ∈ S⟨⟨A^{∗}⟩⟩. We clearly have that

∑_{n=0}^{∞}(r^{n}, ϵ) = ∑_{n=0}^{∞}(r, ϵ)^{n} = (r, ϵ)^{∗}.

Suppose now that u ≠ ϵ. Then (r^{n}, u) = ∑_{u_{1}...u_{n}=u}(r, u_{1}) … (r, u_{n}). Thus, by Ax_{5}, ∑_{n=0}^{∞}(r^{n}, u) exists if the sum ∑_{u_{1}...u_{n}=u, n≥0}(r, u_{1}) … (r, u_{n}) does. But this latter sum indeed exists. This can be seen as follows. For each fixed u_{1}, …, u_{k} ≠ ϵ with u_{1} … u_{k} = u,

∑_{m_{0},...,m_{k}≥0}(r, ϵ)^{m_{0}}(r, u_{1}) … (r, u_{k})(r, ϵ)^{m_{k}} = (r, ϵ)^{∗}(r, u_{1}) … (r, u_{k})(r, ϵ)^{∗}

exists. Since ∑_{u_{1}...u_{n}=u}(r, u_{1}) … (r, u_{n}) is just a finite sum of sums of this form, it follows by Ax_{4} that this sum also exists. Again, only a weak form of Ax_{5} has been used. □

The following fact is clear.

Proposition 12. Suppose that S is a (weak) rationally additive semiring and S′ is a subsemiring of S which is closed under ^{∗}. Say that ∑_{i∈I} s_{i} exists in S′, where s_{i} ∈ S′ for all i ∈ I, if ∑_{i∈I} s_{i} exists in S and belongs to S′, and in that case, let the sum in S′ be the same as in S. Then S′ is also a (weak) rationally additive semiring.

When S is a ^{∗}-semiring and B ⊆ S, the B-rational elements of S are those contained in the ^{∗}-semiring generated by B. Thus the B-rational elements form a ^{∗}-semiring denoted Rat_{S}(B), or just Rat(B). Let S be rationally additive and let A be a set. Then, as shown above, S⟨⟨A^{∗}⟩⟩ is also rationally additive and each a ∈ A and s ∈ S can be conveniently identified with a series in S⟨⟨A^{∗}⟩⟩. We denote S^{rat}⟨⟨A^{∗}⟩⟩ = Rat_{S⟨⟨A^{∗}⟩⟩}(A ∪ S).

The countably additive semiring N_{∞} was defined above.

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

Proof. Clearly, any morphism h : 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 family n_{i}, i ∈ I of nonzero elements of N_{∞}, the sum ∑_{i∈I} n_{i}h exists in S and equals 1^{∗}. But this follows by Proposition 3. □

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

Theorem 15. For each set A, N_{∞}^{rat}⟨⟨A^{∗}⟩⟩ is freely generated by A in the class of rationally additive semirings.

Proof. We need to show that if S is a rationally additive semiring and h is a function A → S, then h has a unique extension to a morphism h^{♯} : N_{∞}^{rat}⟨⟨A^{∗}⟩⟩ → S of rationally additive semirings. Suppose that r ∈ N_{∞}^{rat}⟨⟨A^{∗}⟩⟩. We are forced to define

rh^{♯} = ∑_{(r,u)≠0}(r, u)uh,  (6)

where for any word u = a_{1} … a_{n} ∈ A^{∗} of length n, we define uh = (a_{1}h) · . . . · (a_{n}h). Note that the coefficient (r, u) of uh in (6) is taken in S. This is meaningful, since to each integer n there 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 extend h to a function N_{∞}⟨A⟩ → S, and then to a function (N_{∞}⟨A⟩)^{n×n} → S^{n×n}, for each n ≥ 0. For each n ∈ N_{∞} and a ∈ A we define (na)h = n(ah). For a finite sum ∑_{i∈F} n_{i}a_{i}, we define (∑_{i∈F} n_{i}a_{i})h = ∑_{i∈F} n_{i}(a_{i}h).

We must show that the sum on the right-hand side of (6) exists. Since r is rational, by (a generalization of) Schützenberger’s theorem [see Bloom, Ésik 1993b], there exists α ∈ N_{∞}^{1×n}, M ∈ N_{∞}⟨A⟩^{n×n} and β ∈ N_{∞}^{n×1} with r = αM^{∗}β. Now, by Theorem 9 and Propositions 7 and 8, we have that α(Mh)^{∗}β = ∑_{k=0}^{∞} α(Mh)^{k}β exists. But for each k,

α(Mh)^{k}β = ∑_{|u|=k, (r,u)≠0}(r, u)uh.

Thus, by Ax_{4}, the right-hand side of (6) exists and equals α(Mh)^{∗}β.

Note that for any finite set B ⊆ A such that u ∈ B^{∗} holds for all words u ∈ A^{∗} with (r, u) ≠ 0, i.e., such that supp(r) ⊆ B^{∗}, we have that rh^{♯} = ∑_{u∈B^{∗}}(r, u)uh. We use this fact in our proof that h^{♯} preserves all existing sums. Suppose that r_{i} ∈ N_{∞}^{rat}⟨⟨A^{∗}⟩⟩, i ∈ I such that ∑_{i∈I} r_{i} exists in N_{∞}^{rat}⟨⟨A^{∗}⟩⟩, so that ∑_{i∈I} r_{i} is rational. Since r = ∑_{i∈I} r_{i} is rational, there is a finite set B ⊆ A with supp(r) ⊆ B^{∗}. Clearly then, supp(r_{i}) ⊆ B^{∗} for all i ∈ I. By Ax_{4} and Ax_{5}, the fact that ∑_{i∈I} r_{i}h^{♯} exists and equals rh^{♯} will follow if we can show that the sum ∑_{u∈B^{∗}, i∈I}(r_{i}, u)uh exists and equals rh^{♯}. This in turn will hold if for each fixed u ∈ B^{∗},

∑_{i∈I}(r_{i}, u)uh = (∑_{i∈I}(r_{i}, u))uh

exists and is equal to (r, u)uh. But by Proposition 13, the sum ∑_{i∈I}(r_{i}, u) exists in S, and equals (r, u). □

Corollary 16. There is no rationally additive structure on N_{∞}^{rat}⟨⟨A^{∗}⟩⟩ properly contained in the rationally additive structure inherited from the countably additive structure on N_{∞}⟨⟨A^{∗}⟩⟩.

References

1. [Bloom, Ésik 1993a] Bloom, S. L., Ésik, Z.: “Matrix and Matricial Iteration Theories”; J. Computer and System Sciences, 46, (1993), 381–408.

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

3. [Bloom, Ésik 1997] Bloom, S. L., Ésik, 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; Academic Press (1974).

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

7. [Ésik, Kuich 2001] Ésik, Z., Kuich, W.: “Inductive ^{∗}-Semirings”; to appear.

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

9. [Hebish 1990] Hebisch, U.: “The Kleene Theorem in Countably Complete Semirings”; 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 Semirings”; Proc. ICALP 87, LNCS 267, Springer-Verlag (1987), 212–225.

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

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

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

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

Recent BRICS Report Series Publications

RS-01-42 Zoltán Ésik and Werner Kuich. Rationally Additive Semirings. November 2001. 11 pp.

RS-01-41 Ivan B. Damgård 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án Ésik. 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. October 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 Access to Wavelet Compressed Volumetric Data Using Hashing. August 2001. 31 pp.

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

RS-01-32 Rasmus Pagh and Flemming Friche Rodler. Cuckoo Hashing. August 2001. 21 pp. Short version appears in Meyer auf der Heide, editor, 9th Annual European Symposiumon on Algorithms, ESA ’01 Proceedings, LNCS 2161, 2001, pages 121–