main-content

## Über dieses Buch

Semiring theory stands with a foot in each of two mathematical domains. The first being abstract algebra and the other the fields of applied mathematics such as optimization theory, the theory of discrete-event dynamical systems, automata theory, and formal language theory, as well as from the allied areas of theoretical computer science and theoretical physics. Most important applications of semiring theory in these areas turn out to revolve around the problem of finding the equalizer of a pair of affine maps between two semimodules. In this volume, we chart the state of the art on solving this problem, and present many specific cases of applications.

This book is essentially the third part of a trilogy, along with Semirings and their Applications, and Power Algebras over Semirings, both written by the same author and published by Kluwer Academic Publishers in 1999. While each book can be read independently of the others, to get the full force of the theory and applications one should have access to all three.

This work will be of interest to academic and industrial researchers and graduate students. The intent of the book is to bring the applications to the attention of the abstract mathematicians and to make the abstract mathematics available to those who are using these tools in an ad-hoc manner without realizing the full force of the theory.

## Inhaltsverzeichnis

### Chapter 1. Semirings

Abstract
A semiring (R, +,•) is a nonempty set R on which we have defined operations of addition and multiplication satisfying the following conditions:
(1)
(R, +) is a commutative monoid with identity element 0;

(2)
(R, •) is a monoid with identity element 1 ≠ 0;

(3)
a(b + c) = ab+ ac and (a + b)c — ac + bc for all a, b, c ∈ R;

(4)
0a = 0 = a0 for all a ∈ R.

Jonathan S. Golan

### Chapter 2. Partially-ordered semirings

Abstract
A semiring R is partially ordered if and only if there exists a partial order relation ≤ on R satisfying the following conditions for all a, b, cR:
(1)
If ab then a + cb + c;

(2)
If ab and 0 ≤ c then acbc and cacb.

Jonathan S. Golan

### Chapter 3. Complete semirings

Abstract
In many common semirings there is a possibility of infinite summation, and so we need to consider that possibility too. In particular, a semiring R is complete if and only if to each function f: Ω → R, where Ω is a nonempty set, we can assign a value Σf in R such that the following conditions are satisfied:
(1)
If Ω = {i 1,..., i n } is a finite set then Σf = f(i 1) + ... + f(i n );

(2)
If rR then Σ(rf)=rf] and Σ(fr) = [Σf]r;

(3)
If Ω = U j∈Λ Ω j is a partition of Ω into a disjoint union of nonempty subsets and if f j is the restriction of f to Ω j for each j ∈ Ω then the function g: Λ → R defined by g : j ↦ Σf j satisfies Σg = Σf. Every complete semiring has an infinite element (see Proposition 22.27 of [215]). For a comprehensive study of infinite sums in semirings, refer to [251].

Jonathan S. Golan

### Chapter 4. Residuated semirings

Abstract
We begin with a notion from the theory of partially-ordered sets. A function f from a partially-ordered set A to a partially-ordered set B is isotone if and only if a ≤ a’ in A implies that f (a) ≤ f (a’) in B. Thus, if R is a partially-ordered semiring, the functions rrc and rrc from R to itself are isotone, for every 0 ≤ c i?. An isotone function / from a partially-ordered set A to a partially-ordered set B is residuated if and only if for each b e B there exists an element a ∈ A satisfying the condition that f (a’) ≤ b if and only if a’ ≤ a. Such an element a, if it exists, is clearly unique, and we denote it by f <-1>(b).
Jonathan S. Golan

### Chapter 5. Matrix semirings

Abstract
If n is a positive integer and R is a semiring then the collection M n (R) of all n × n matrices over R is again a semiring, the addition in which is componentwise and multiplication in which is given by the usual rule of matrix multiplication: if A = [a ij ] and B = [b ij ] are such matrices then AB = [c ij ] where $${c_{ij}}\sum\nolimits_{h = 1}^n {{a_{ih}}{b_{hj}}}$$ for all 1 ≤ i,j ≤ n. An analysis of the time needed to perform multiplication of matrices over finite semirings is given in [413]. The additive identity of M n (R) is, as one would expect, the matrix O having all of its entries equal to 0, and the multiplicative identity is the matrix I all of the entries on the diagonal of which are equal to 1 while all other entries are equal to 0.
Jonathan S. Golan

### Chapter 6. Symmetric extension of a semiring

Abstract
Let R be a semiring and let Iideal(R). Then it is easy to verify that
$${{\mathcal{D}}_{2}}\left( {R,I} \right) = \left\{ {\left[ {\begin{array}{*{20}{c}} a & b \\ b & a \\ \end{array} } \right] \in {{\mathcal{M}}_{2}}\left( R \right)\left| {a \in R\,and\,b \in I} \right.} \right\}$$
is a subsemiring of M 2(R). This semiring is additively idempotent if and only if R is, and is commutative if and only if R is.
Jonathan S. Golan

### Chapter 7. Semimodules

Abstract
Let R be a semiring. A left R -semimodule is an additive abelian monoid (M, +) with additive identity 0 M for which we have a function R × MM denoted by (r, m) ↦ rm, called scalar multiplication, which satisfies the following conditions for all r,yR and all m,m’, ∈ G M:
(1)
(rr’)mr(rm);

(2)
r(m + m’) = rm + rm’;

(3)
(r + r’)m = rm + rm;

(4)
1m = m;

(5)
r0 M = 0 M = 0m.

Jonathan S. Golan

### Chapter 8. Homomorphisms between semimodules

Abstract
Let R be a semiring and let M and M’ be left R-semimodules. A function α: M → M’, written as acting on the right, is an R-homomorphism if and only if (m + m’)a = ma + m’α and (rm)α = r(ma) for all r ∈ R and all m, m’ G M: We denote the set of all R-homomorphisms from M to M’ by Hom R (M,M’). This set is always nonempty since it contains the 0-homomorphism Σ0 : m ↦ 0m’, If α G Hom R (M, M’), then the image im(α) = { | mM} of a is a subsemimodule of M’ and the kernel ker(α) = {m G M | ma = 0m’} of α is a subsemimodule of M. Note that the kernel of α may equal {0 m } even though α is far from being monic. Similarly we define the notion of an R-homomorphism of right i?-semimodules. Such functions are written as acting on the left. An R-homomorphism which is monic and epic is an R-isomorphism. If m ∈ M is idempotent, and if α ∈ Hom R (M,M’), then ma is an idempotent element of M’;. If N is a subsemimodule of a left R-semimodule M, and if a ∈ Hom R (M,M’), then the restriction of a to N is clearly an iž-homomorphism from N to M’.
Jonathan S. Golan

### Chapter 9. Affine maps between semimodules

Abstract
Let R be a semiring and let M and M’ be left R-semimodules. Each element u of M’ defines a constant function k u : M → M’ given by k u : m → u for each m G M. An affine map from M to M’ is a function from M to M’ of the form ? α,u = α + K u , where αHom R (M, M’) and iz u ∈ M’. We will denote the set of all affine maps from M to M’ by Aff R (M,M’). In particular, we see that Hom R (M, M’) ⊆ Aff R (M, M’). Affine maps between left R-semimodules will, like homomorphisms, be written as acting on the right.
Jonathan S. Golan

### Chapter 10. Partially-ordered semimodules

Abstract
Let R be a partially-ordered semiring. A left R-semimodule M is partially ordered if and only if there exists a partial-order relation ≤ defined on M satisfying the following conditions:
(1)
If mm’ in M and if m“ ∈ M then m + m” ≤ m’ + m“,

(2)
If mm’ in M and if 0 ≤ a in R then amam’;

(3)
If ab in R and 0 M m in M then ambm.

Jonathan S. Golan

### Chapter 11. Eigenelements

Abstract
Let M be a left i?-semimodule and let α be an R-endomorphism of M. An element m ? 0m of M is an eigenelement of α if and only if there exists an element r of R satisfying ma — rm. In that case, r is the eigenvalue of α associated with m. A pair (r,m)R × M consisting of an eigenvalue of α along with an eigenelement to which it is associated, is called an eigenpair for α. The set of all eigenvalues of α associated with its various eigenelements is called the spectrum of α and is denoted by spec(α). Note that 0 ∈ spec(α) if and only if ker(α) is nontrivial. In this case we say that α is singular; otherwise it is nonsingular.
Jonathan S. Golan

### Chapter 12. Permanents and determinants

Abstract
Due to the lack of additive inverses in general semirings, we cannot define the notion of a determinant of a square matrix over a semiring i?, in the classical sense. There are, however, three possibilities to get around this problem, at least partially: we can make use of permanents of matrices over R instead of determinants; we can define and use the notion of the bideter minant of a matrix over R which takes values in (Math), as was first proposed by [314]; or we can consider the determinant of matrices over the symmetric extension of R. In this chapter, we briefly survey all three possibilities.
Jonathan S. Golan

### Backmatter

Weitere Informationen