nach oben

2003 | Buch

Kapitel lesen Erstes Kapitel lesen

Semirings and Affine Equations over Them: Theory and Applications

verfasst von: Jonathan S. Golan

Verlag: Springer Netherlands

Buchreihe : Mathematics and Its Applications

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten

Ü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

Frontmatter

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, c ∈ R:

(1)

If a ≤ b then a + c≤b + c;

(2)

If a ≤ b and 0 ≤ c then ac ≤ bc and ca ≤ cb.

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 ₁,..., i _n} is a finite set then Σf = f(i ₁) + ... + f(i _n);

(2)

If r ∈ R then Σ(rf)=r[Σf] 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 r → rc and r → rc 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 I ∈ ideal(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 ₂(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_Mfor which we have a function R × M → M denoted by (r, m) ↦ rm, called scalar multiplication, which satisfies the following conditions for all r,y ∈ R and all m,m’, ∈ G M:

(1)

(rr’)m — r(r’m);

(2)

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

(3)

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

(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 ↦ 0_m’, If α G Hom _R (M, M’), then the image im(α) = {mα | m ∈ M} 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 m ≤ m’ in M and if m“ ∈ M then m + m” ≤ m’ + m“,

(2)

If m ≤ m’ in M and if 0 ≤ a in R then am ≤ am’;

(3)

If a ≤ b in R and 0_M ≤ m in M then am ≤ bm.

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 ? 0_m 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

Titel: Semirings and Affine Equations over Them: Theory and Applications
verfasst von: Jonathan S. Golan
Verlag: Springer Netherlands
Electronic ISBN: 978-94-017-0383-3
Print ISBN: 978-90-481-6310-6
DOI: https://doi.org/10.1007/978-94-017-0383-3

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

Chapter 1. Semirings

Chapter 2. Partially-ordered semirings

Chapter 3. Complete semirings

Chapter 4. Residuated semirings

Chapter 5. Matrix semirings

Chapter 6. Symmetric extension of a semiring

Chapter 7. Semimodules

Chapter 8. Homomorphisms between semimodules

Chapter 9. Affine maps between semimodules

Chapter 10. Partially-ordered semimodules

Chapter 11. Eigenelements

Chapter 12. Permanents and determinants

Backmatter