# (

Authors: Syed Eqbal Alam; Shrisha Rao; Bijan Davvaz
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

We propose a new class of mathematical structures called(m,n)-semirings (which generalize the usual semirings) and describe their basic properties. We define partial ordering and generalize the concepts of congruence, homomorphism, and so forth, for (m,n)-semirings. Following earlier work by Rao (2008), we consider systems made up of several components whose failures may cause them to fail and represent the set of such systems algebraically as an (m,n)-semiring. Based on the characteristics of these components, we present a formalism to compare the fault-tolerance behavior of two systems using our framework of a partially ordered (m,n)-semiring.


---

## Body

## 1. Introduction

Fault tolerance is the property of a system to be functional even if some of its components fail. It is a very critical issue in the design of the systems as in Air Traffic Control Systems [1, 2], real-time embedded systems [3], robotics [4, 5], automation systems [6, 7], medical systems [8], mission critical systems [9], and a lot of others. Description of fault-tolerance modeling using algebraic structures is proposed by Beckmann [10] for groups and by Hadjicostis [11] for semigroups and semirings. Semirings are also used in other areas of computer science like cryptography [12], databases [13], graph theory, game theory [14], and so forth. Rao [15] uses the formalism of semirings to analyze the fault tolerance of a system as a function of its composition, with a partial ordering relation between systems used to compare their fault-tolerance behaviors.The generalization of algebraic structures was in active research for a long time; Timm [16] in 1967 proposed commutative n-groups; later Crombez [17] in 1972 generalized rings and named it as (m,n)-rings. It was further studied by Crombez and Timm [18], Leeson and Butson [19, 20], and by Dudek [21]. Recently the generalization of algebraic structures is studied Davvaz et al. [22, 23].In this paper, we first define the(m,n)-semiring (ℛ,f,g) (which is a generalization of the ordinary semiring (ℛ,+,×), where ℛ is a set with binary operations + and ×), using f and g which are m-ary and n-ary operations, respectively. We propose identity elements, multiplicatively absorbing elements, idempotents, and homomorphisms for (m,n)-semirings. We also briefly touch on zero-divisor free, zero-sum free, additively cancellative, and multiplicatively cancellative (m,n)-semirings and the congruence relation on (m,n)-semirings. In Section 4, we use the facts that each system consists of components or subsystems and that the fault-tolerance behavior of the system depends on each of the components or subsystems that constitute the system. A system may itself be a module or part of a larger system, so that its fault tolerance affects that of the whole system of which it is a part. We analyze the fault tolerance of a system given its composition, extending earlier work of Rao [15]. Section 2 describes the notations used and the general conventions followed.Section3 deals with the definition and properties of (m,n)-semirings. In Section 4, we extend the results of Rao [15] using a partial ordering on the (m,n)-semiring of systems: the class of systems is algebraically represented by an (m,n)-semiring, and the fault-tolerance behavior of two systems is compared using partially ordered (m,n)-semiring.


## 2. Preliminaries

The set of integers is denoted byℤ, with ℤ+ and ℤ- denoting the sets of positive integers and negative integers, respectively, and m and n used are positive integers. Let ℛ be a set and f a mapping f:ℛm→ℛ; that is, f is an m-ary operation. Elements of the set ℛ are denoted by xi,yi where i∈ℤ+.Definition 1.
A nonempty setℛ with an m-ary operation f is called an m-ary groupoid and is denoted by (ℛ,f) (see Dudek [24]).We use the following general convention.The sequencexi,xi+1,…,xm is denoted by xim where 1≤i≤m.For all1≤i≤j≤m, the following term
(1)f(x1,…,xi,yi+1,…,yj,zj+1,…,zm)
is represented as
(2)f(x1i,yi+1j,zj+1m).In the case whenyi+1=⋯=yj=y, (2) is expressed as
(3)f(x1i,y(j-i),zj+1m).Definition 2.
Letx1,x2,…,x2m-1 be elements of set ℛ.(i)
Then, the associativity and distributivity laws for them-ary operation f are defined as follows.
(a)
Associativity:
(4)f(x1i-1,f(xim+i-1),xm+i2m-1)=f(x1j-1,f(xjm+j-1),xm+j2m-1),for allx1,…,x2m-1∈ℛ, for all 1≤i≤j≤m (from Gluskin [25]).(b)
Commutativity:
(5)f(x1,x2,…,xm)=f(xη(1),xη(2),…,xη(m)),for every permutationη of {1,2,…,m} (from Timm [16]), ∀x1,x2,…,xm∈ℛ.(ii)
Anm-ary groupoid (ℛ,f) is called an m-ary semigroup if f is associative (from Dudek [24]); that is, if
(6)f(x1i-1,f(xim+i-1),xm+i2m-1)=f(x1j-1,f(xjm+j-1),xm+j2m-1),for allx1,…,x2m-1∈ℛ, where 1≤i≤j≤m.(iii)
Letx1,x2,…,xn, a1,a2,…,am be elements of set ℛ, and 1≤i≤n. The n-ary operation g is distributive with respect to the m-ary operation f if
(7)g(x1i-1,f(a1m),xi+1n)=f(g(x1i-1,a1,xi+1n),…,g(x1i-1,am,xi+1n)).Remark 3.
(i) Anm-ary semigroup (ℛ,f) is called a semiabelian or (1,m)-commutative if
(8)f(x,a,…,a︸m-2,y)=f(y,a,…,a︸m-2,x),
for all x,y,a∈ℛ (from Dudek and Mukhin [26]).
(ii) Consider ak-ary group (G,h) in which the k-ary operation h is distributive with respect to itself, that is,
(9)h(x1i-1,h(a1k),xi+1k)=h(h(x1i-1,a1,xi+1k),…,h(x1i-1,ak,xi+1k)),
for all 1≤i≤k. These types of groups are called autodistributivek-ary groups (see Dudek [27]).


## 3.(m,n)-Semirings and Their Properties

Definition 4.
An(m,n)-semiring is an algebraic structure (ℛ,f,g) which satisfies the following axioms:(i)
(ℛ,f) is an m-ary semigroup,(ii)
(ℛ,g) is an n-ary semigroup,(iii)
then-ary operation g is distributive with respect to the m-ary operation f.Example 5.
Letℬ be any Boolean algebra. Then, (ℬ,f,g) is an (m,n)-semiring where f(A1m)=A1∪A2∪⋯∪Am and g(B1n)=B1∩B2∩⋯∩Bn, for all A1,A2,…,Am and B1,B2,…,Bn∈ℬ.In general, we have the following.Theorem 6.
Let(ℛ,+,×) be an ordinary semiring. Let f be an m-ary operation and g be an n-ary operation on ℛ as follows:
(10)f(x1m)=∑i=1m‍xi,∀x1,x2,…,xm∈ℛ,g(y1n)=∏i=1n‍yi,∀y1,y2,…,yn∈ℛ.
Then, (ℛ,f,g) is an (m,n)-semiring.Proof.
Omitted as obvious.Example 7.
The following give us some(m,n)-semirings in different ways indicated by Theorem 6.(i)
Let(ℛ,+,×) be an ordinary semiring and x1,x2,…,xn be in ℛ. If we set
(11)g(x1n)=x1×x2×⋯×xn,we get a(2,n)-semiring (ℛ,+,g).(ii)
In an(m,n)-semiring (ℛ,f,g), fixing elements a2m-1 and b2n-1, we obtain two binary operations as follows:
(12)x⊕y=f(x,a2m-1,y),x⊗y=g(x,b2n-1,y).Obviously,(ℛ,⊕,⊗) is a semiring.(iii)
The setℤ- of all negative integers is not closed under the binary products; that is, ℤ- does not form a semiring, but it is a (2,3)-semiring.Definition 8.
Let(ℛ,f,g) be an (m,n)-semiring. Then m-ary semigroup (ℛ,f) has an identity element0 if
(13)x=f(0,…,0︸i-1,x,0,…,0︸m-i),
for all x∈ℛ and 1≤i≤m. We call 0 as an identity element of (m,n)-semiring (ℛ,f,g).
Similarly,n-ary semigroup (ℛ,g) has an identity element1 if
(14)y=g(1,…,1︸j-1,y,1,…,1︸n-j),
for all y∈ℛ and 1≤j≤n.
We call1 as an identity element of (m,n)-semiring (ℛ,f,g).
We therefore call0 the f-identity, and 1 the g-identity.Remark 9.
In an(m,n)-semiring (ℛ,f,g), placing 0 and 1, (m-2) and (n-2) times, respectively, we obtain the following binary operations:
(15)x+y=f(x,0,…,0︸m-2,y),x×y=g(x,1,…,1︸n-2,y),∀x,y∈ℛ.Definition 10.
Let(ℛ,f,g) be an (m,n)-semiring with an f-identity element 0 and g-identity element 1. Then,(i)
0 is said to be multiplicatively absorbing if it is absorbing in (ℛ,g), that is, if
(16)g(0,x1n-1)=g(x1n-1,0)=0,for allx1,x2,…,xn-1∈ℛ.(ii)
(ℛ,f,g) is called zero-divisor free if
(17)g(x1,x2,…,xn)=0always impliesx1=0 or x2=0 or ⋯ or xn=0.Elementsx1,x2,…,xn-1∈ℛ are called left zero-divisors of (m,n)-semiring (ℛ,f,g) if there exists a≠0 and the following holds:
(18)g(x1n-1,a)=0.(iii)
(ℛ,f,g) is called zero-sum free if
(19)f(x1,x2,…,xm)=0always impliesx1=x2=⋯=xm=0.(iv)
(ℛ,f,g) is called additively cancellative if the m-ary semigroup (ℛ,f) is cancellative, that is,
(20)f(x1i-1,a,xi+1m)=f(x1i-1,b,xi+1m)⇒a=b,for alla,b,x1,x2,…,xm∈ℛ and for all 1≤i≤m.(v)
(ℛ,f,g) is called multiplicatively cancellative if the n-ary semigroup (ℛ,g) is cancellative, that is,
(21)g(x1i-1,a,xi+1n)=g(x1i-1,b,xi+1n)⇒a=b,for alla,b,x1,x2,…,xn∈ℛ and for all 1≤i≤n.Elementsx1,x2,…,xn-1 are called left cancellable in an n-ary semigroup (ℛ,g) if
(22)g(x1n-1,a)=g(x1n-1,b)⇒a=b,for allx1,x2,…,xn-1,a,b∈ℛ.(ℛ,f,g) is called multiplicatively left cancellative if elements x1,x2,…,xn-1∈ℛ∖{0} are multiplicatively left cancellable in n-ary semigroup (ℛ,g).Theorem 11.
Let(ℛ,f,g) be an (m,n)-semiring with f-identity 0.(i)
If elementsx1,x2,…,xn-1∈ℛ are multiplicatively left cancellable, then elements x1,x2,…,xn-1 are not left divisors.(ii)
If the(m,n)-semiring (ℛ,f,g) is multiplicatively left cancellative, then it is zero-divisor free.We have generalized Theorem11 from Theorem 4.4 of Hebisch and Weinert [28].We have generalized the definition of idempotents of semirings given by Bourne [29] and Hebisch and Weinert [28]), as follows.Definition 12.
Let(ℛ,f,g) be an (m,n)-semiring. Then,(i)
it is calledadditively idempotent if (ℛ,f) is an idempotent m-ary semigroup, that is, if
(23)f(x,x,…,x︸m)=x,for allx∈ℛ;(ii)
it is calledmultiplicatively idempotent if (ℛ,g) is an idempotent n-ary semigroup, that is, if
(24)g(y,y,…,y︸n)=y,for ally∈ℛ, y≠0.Theorem 13.
An(m,n)-semiring (ℛ,f,g) having at least two multiplicatively idempotent elements in the center is not multiplicatively cancellative.Proof.
Leta and b be two multiplicatively idempotent elements in the center, a≠b. Then,
(25)g(1,…,1︸n-2,a,b)=g(1,…,1︸n-2,b,a),
which can be written as follows:
(26)g(1,…,1︸n-2,g(a)(n),b)=g(1,…,1︸n-2,g(b)(n),a),
which is represented as
(27)g(1,…,1︸n-3,g(1,a(n-1)),a,b)=g(1,…,1︸n-3,g(1,b(n-1)),b,a).
If the(m,n)-semiring (ℛ,f,g) is multiplicatively cancellative, then the following holds true:
(28)g(1,…,1︸n-3,g(1,a(n-1)),1,1)=g(1,…,1︸n-3,g(1,b(n-1)),1,1),g(1,a(n-1))=g(1,b(n-1)),
which implies that a=b, which is a contradiction to the assumption that a≠b; therefore, (ℛ,f,g) is not multiplicatively cancellative.We have generalized Exercise 2.7 in ChapterI of Hebisch and Weinert [28] to get the following.Definition 14.
Let (ℛ,f,g) be an (m,n)-semiring and σ an equivalence relation on ℛ. (i)
Then,σ is called a congruence relation or a congruence of (ℛ,f,g), if it satisfies the following properties for all 1≤i≤m and 1≤j≤n:
(a)
ifxiσyi then f(x1m)σf(y1m),(b)
ifzjσuj then g(z1n)σg(u1n),for allx1,x2,…,xm, y1,y2,…,ym, z1,z2,…,zn, u1,u2,…,un∈ℛ.(ii)
Letσ be a congruence on an algebra ℛ. Then, the quotient of ℛ by σ, written as ℛ/σ, is the algebra whose universe is ℛ/σ and whose fundamental operation satisfies
(29)fℛ/σ(x1,x2,…,xm)=fℛ(x1,x2,…,xm)σ,wherex1,x2,…,xm∈ℛ [30].Theorem 15.
Let(ℛ,f,g) be an (m,n)-semiring and the relation σ be a congruence relation on (ℛ,f,g). Then, the quotient (ℛ/σ,F,G) is an (m,n)-semiring under F((x1)/σ,…,(xm)/σ)=f(x1m)/σ and G((y1)/σ,…,(yn)/σ)=g(y1n)/σ, for all x1,x2,…,xm and y1,y2,…,yn in ℛ.Proof.
Omitted as obvious.Definition 16.
We define homomorphism, isomorphism, and a product of two mappings as follows.(i)
A mappingφ:ℛ→𝒮 from (m,n)-semiring (ℛ,f,g) into (m,n)-semiring (𝒮,f′,g′) is called a homomorphism if
(30)φ(f(x1m))=f′(φ(x1),φ(x2),…,φ(xm)),φ(g(y1n))=g′(φ(y1),φ(y2),…,φ(yn)),for allx1,x2,…,xm, y1,y2,…,yn∈ℛ.(ii)
The(m,n)-semirings (ℛ,f,g) and (𝒮,f′,g′) are called isomorphic if there exists one-to-one homomorphism from ℛ onto 𝒮. One-to-one homomorphism is called isomorphism.(iii)
If we apply mappingφ:ℛ→𝒮 and then ψ:𝒮→𝒯 on x, we get the mapping (ψ∘φ)(x) which is equal to ψ(φ(x)), where x∈ℛ. It is called the product of ψ and φ [28].We have generalized Definition16 from Definition 2 of Allen [31].We have generalized the following theorem from Theorem3.3 given by Hebisch and Weinert [28].Theorem 17.
Let(ℛ,f,g), (𝒮,f′,g′), and (𝒯,f′′,g′′) be (m,n)-semirings. Then, if the following mappings φ:(ℛ,f,g)→(𝒮,f′,g′) andψ:(𝒮,f′,g′)→(𝒯,f′′,g′′) are homomorphisms; then,ψ∘φ:(ℛ,f,g)→(𝒯,f′′,g′′) is also a homomorphism.Proof.
Letx1,x2,…,xm and y1,y2,…,yn be in ℛ. Then
(31)(ψ∘φ)(f(x1m))=ψ(φ(f(x1,x2,…,xm)))=ψ(f′(φ(x1),φ(x2),…,φ(xm)))=f′′(ψ(φ(x1)),ψ(φ(x2)),…,ψ(φ(xm)))=f′′((ψ∘φ)(x1),(ψ∘φ)(x2),…,(ψ∘φ)(xm)).
In a similar manner, we can deduce that
(32)(ψ∘φ)(g(y1n))=g′′((ψ∘φ)(y1),(ψ∘φ)(y2),…,(ψ∘φ)(yn)).
Thus, it is evident that ψ∘φ is a homomorphism from ℛ→𝒯.This proof is similar to that of Theorem 6.5 given by Burris and Sankappanavar [30].Definition 18.
Let(ℛ,f,g) and (𝒮,f′,g′) be (m,n)-semirings and φ:ℛ→𝒮 a homomorphism. Then, the kernel of φ, written as ker φ, is defined as follows:
(33)kerφ={(a,b)∈ℛ×ℛ∣φ(a)=φ(b)}.
Generalization of Burris and Sankappanavar [30].Theorem 19.
Let(ℛ,f,g) and (𝒮,f′,g′) be (m,n)-semirings and φ:ℛ→𝒮 a homomorphism. Then, kerφ is a congruence relation on ℛ, and there exists a unique one-to-one homomorphism ψ from ℛ/kerφ into 𝒮.Proof.
Omitted as obvious.Corollary 20.
Let(ℛ,f,g) be an (m,n)-semiring and ρ and σ congruence relations on ℛ, with ρ⊆σ. Then, σ/ρ={ρ(x),ρ(y)∣(x,y)∈σ} is a congruence relation on ℛ/ρ, and (ℛ/ρ)/(σ/ρ)≅ℛ/σ.Lemma 21.
Letx1,x2,…,xm, y1,y2,…,yn∈ℛ. Then,(i)
f(f(…f(f︸m(x1,0,…,0︸m-1),x2,0,…,0︸m-2),…), xm,0,…,0︸m-2)=f(x1,x2,…,xm),(ii)
g(g(…g(g︸n(y1,1,…,1︸n-1),y2,1,…,1︸n-2),…), yn,1,…,1︸n-2)=g(y1,y2,…,yn).Proof.
(i)(34)f(f(…f(f︸m(x1,0,…,0︸m-1),x2,0,…,0︸m-2),…),xm,0,…,0︸m-2).
By associativity (Definition 2 (i)), (34) is equal to
(35)f(f(…f(f︸m(0,0,…,0︸m-1),x1,x2,0,…,0︸m-3),…),xm,0,…,0︸m-2)=f(f(…f(f︸m-1(0,x1,x2,0,…,0︸m-3),x3,0,…,0︸m-2),…),xm,0,…,0︸m-2)=f(f(…f(f︸m-1(0,…,0︸m),x1,x2,x3,0,…,0︸m-4),…),xm,0,…,0︸m-2)=f(f(…f(f︸m-2(0,x1,x2,x3,0,…,0︸m-4),x4,0,…,0︸m-2),…),xm,0,…,0︸m-2)=f(f(…f(f︸m-2(0,x1,x2,x3⋮=f(f(x1,x2,…,xm-1,0),xm,0,…,0︸m-2)=f(f(x1,x2,…,xm-1,xm),0,…,0︸m-1)=f(x1,x2,…,xm).
(ii) Similar to part (i).


## 4. Partial Ordering on Fault Tolerance

In this sections we usexi,yi, and so forth, where i∈ℤ+ to denote individual system components that are assumed to be atomic at the level of discussion; that is, they have no components or subsystems of their own. We use component to refer to such an atomic part of a system, and subsystem to refer to a part of a system that is not necessarily atomic. We assume that components and subsystems are disjoint, in the sense that if they fail, they fail  independently and do not affect the functioning of other components.Let𝒰 be a universal set of all systems in the domain of discourse as given by Rao [15], and let f be a mapping f:𝒰m→𝒰, that is, f is an m-ary operation. Likewise, let g be an n-ary operation.Definition 22.
We definef and g operations for systems as follows.(i)
f is an m-ary operation which applies on systems made up of m components or subsystems, where if any one of the components or subsystems fails, then the whole system fails.If a system made up ofm components x1,x2,…,xm, then, the system over operation f is represented as f(x1,x2,…,xm) for all x1,x2,…,xm∈𝒰. The system f(x1,x2,…,xm) fails when any of the components x1,x2,…,xm fails.(ii)
g is an n-ary operation which applies on a system consisting of n components or subsystems, which fails if all the components or subsystems fail; otherwise it continues working even if a single component or subsystem is working properly.Let a system consist ofn components x1,x2,…,xn, then, the system over operation g is represented as g(x1,x2,…,xn) for all x1,x2,…,xn∈𝒰. The system g(x1,x2,…,xn) fails when all the components x1,x2,…,xn fail.Consider a partial ordering relation≼ on 𝒰, such that (𝒰,≼) is a partially ordered set (poset). This is a fault-tolerance partial ordering where f(x1m)≼f(y1m) means that f(x1m) has a lower measure of some fault metric than f(y1m) and f(x1m) has a better fault tolerance than f(y1m), for all f(x1m),f(y1m)∈𝒰 (see Rao [32] for more details) and x1,x2,…,xm, y1,y2,…,ym are disjoint components.Assume that0 represents the atomic system “which is always up” and 1 represents the system “which is always down” (see Rao [32]).Observation 23.
We observe the following for all disjoint componentsx1,x2,…,xm, y1,y2,…,yn, which are in 𝒰.(i)
g(y1j-1,0,yj+1n)=0 for all 1≤j≤n.This is so since0 represents the component or system which never fails, and as per the definition of g, the system as a whole fails if all the components fail, and otherwise it continues working even if a single component is working properly. In a system g(y1j-1,0,yj+1n), even if all other components y1j-1 and yj+1n fail even then 0 is up and the system is always up.(ii)
f(x1i-1,1,xi+1m)=1 for all 1≤i≤m.This is so since1 represents the component or system which is always down, and as per the definition of f if either of the component fails, then the whole system fails. Thus, even though all other components are working properly but due to the component 1 the system is always down.Definition 24.
If(𝒰,f,g) is an (m,n)-semiring and (𝒰,≼) is a poset, then (𝒰,f,g,≼) is a partially ordered(m,n)-semiring if the following conditions are satisfied for all x1,x2,…,xm, y1,y2,…,yn, a,b∈𝒰 and 1≤i≤m, 1≤j≤n.(i)
Ifa≼b, then f(x1i-1,a,xi+1m)≼f(x1i-1,b,xi+1m).(ii)
Ifa≼b, then g(y1j-1,a,yj+1n)≼g(y1j-1,b,yj+1n).Remark 25.
As it is assumed that0 is the system which is always up, it is more fault tolerant than any of the other systems or components. Therefore 0≼a, for all a∈𝒰. Similarly, a≼1 because 1 is the system that always fails, and therefore, it is the least fault tolerant; every other system is more fault tolerant than it.Observation 26.
The following are obtained for all disjoint componentsr, s, xi, yj, ai, bj, which are in 𝒰, where 1≤i≤m, 1≤j≤n.(i)
0≼f(x1i-1,r,xi+1m)≼1.(ii)
0≼g(y1j-1,s,yj+1n)≼1.(iii)
0≼g(y1j-1,f(a1m),yj+1n)≼1.(iv)
0≼f(x1i-1,g(b1n),xi+1m)≼1.From the above description of0 and 1, the observation is quite obvious. Case (i) shows that 0 is less faulty than f(x1i-1,r,xi+1m), and f(x1i-1,r,xi+1m) is less faulty than 1. Similarly, case (ii) shows that 0 is more fault tolerant than g(y1j-1,s,yj+1n) and g(y1j-1,s,yj+1n) is more fault tolerant than 1. Likewise, case (iii) shows the operation g over y1j-1, yj+1n and f of a1m to be less faulty than 1 and more faulty than 0, and a similar interpretation is made for (iv).Lemma 27.
If≼ is a fault-tolerance partial order and x1,x2,…,xm, y1,y2,…,ym, z1,z2,…,zn, u1,u2,…,un are disjoint components, which are in 𝒰, where m,n∈ℤ+, then for all 1≤i≤m and 1≤j≤n the following holds true:(i)
ifxi≼yi, then f(x1m)≼f(y1m),(ii)
ifzj≼uj, then g(z1n)≼g(u1n).Proof.
(i) Sincexi≼yi for all 1≤i≤m, we have
(36)x1≼y1,
which is represented as follows:
(37)f(0,…,0︸m-1,x1)≼f(0,…,0︸m-1,y1),(38)f(0,…,0︸m-1,x2)≼f(0,…,0︸m-1,y2).
By f operation on both sides of (37) with y2, we get
(39)f(f(0,…,0︸m-1,x1),y2,0,…,0︸m-2)≼f(f(0,…,0︸m-1,y1),y2,0,…,0︸m-2).
By f operation on both sides of (38) with x1(40)f(f(0,…,0︸m-1,x2),x1,0,…,0︸m-2)≼f(f(0,…,0︸m-1,y2),x1,0,…,0︸m-2).
From (39) and (40), we get
(41)f(f(0,…,0︸m-1,x1),y2,0,…,0︸m-2)≼f(f(0,…,0︸m-1,y1),y2,0,…,0︸m-2).
Similarly, we find for m terms
(42)f(…(f(f︸m(0,…,0︸m-1,x1),x2,0,…,0︸m-2),…),xm,0,…,0︸m-2)≼f(…(f(f︸m(0,…,0︸m-1,y1),y2,0,…,0︸m-2),…),ym,0,…,0︸m-2).
From Lemma 21, (42) may be represented as
(43)f(x1,x2,…,xm)≼f(y1,y2,…,ym)
so
(44)f(x1m)≼f(y1m).
(ii)  Sincezj≼yj, for all 1≤j≤n(45)g(1,…,1︸n-1,z1)≼g(1,…,1︸n-1,u1)g(1,…,1︸n-1,z2)≼g(1,…,1︸n-1,u2).
After following similar steps as seen in part (i), we use the g operation for n terms,
(46)g(…(g(g︸n(1,…,1︸n-1,z1),z2,1,…,1︸n-2),…),zn,1,…,1︸n-2)≼g(…(g(g︸n(1,…,1︸n-1,u1),u2,1,…,1︸n-2),…),un,1,…,1︸n-2),
which is represented as
(47)g(z1,z2,…,zn)≼g(u1,u2,…,un),
and so
(48)g(z1n)≼g(u1n).Theorem 28.
If≼ is a fault-tolerance partial order and given disjoint components ai, cj, bi, dj in 𝒰, where 1≤i≤m, 1≤j≤n and 1≤k≤m, the following obtain.(i)
Ifai≼bi, then
(49)g(y1j-1,f(a1m),yj+1n)≼g(y1j-1,f(b1m),yj+1n)∀y1,y2,…,yn∈𝒰.(ii)
Ifcj≼dj, then
(50)f(x1k-1,g(c1n),xk+1m)≼f(x1k-1,g(d1n),xk+1m)∀x1,x2,…,xm∈𝒰.Proof.
(i)  Sinceai≼bi, for all 1≤i≤m.
Therefore, from Lemma27 (i)
(51)f(a1m)≼f(b1m),∀a1,a2,…,am,b1,b2,…,bm∈𝒰.
From Definition 24 of a partially ordered (m,n)-semiring, we deduce that
(52)g(y1j-1,f(a1m),yj+1n)≼g(y1j-1,f(b1m),yj+1n),
for all 1≤j≤n.
(ii)  Sincecj≼dj, for all 1≤j≤n, from Lemma 27 (ii), we find that
(53)g(c1n)≼g(d1n),∀c1,c2,…,cn,d1,d2,…,dn∈𝒰.
From Definition 24 of a partially ordered (m,n)-semiring, we deduce that
(54)f(x1k-1,g(c1n),xk+1m)≼f(x1k-1,g(d1n),xk+1m),
for all 1≤k≤m.Lemma 29.
If≼ is a fault-tolerance partial order and xi,yj are disjoint components which are in 𝒰, where 1≤i≤m and 1≤j≤n, one gets the following:(i)
xi≼f(x1,x2,…,xm),(ii)
g(y1,y2,…,yn)≼yj.Proof.
(i) As(55)0≼x1,
by f operation on both sides of (55) with xi, we get
(56)f(0,xi,0,…,0︸m-2)≼f(x1,xi,0,…,0︸m-2).
Therefore,
(57)xi≼f(x1,xi,0,…,0︸m-2).
Similarly, we obtain
(58)xi≼f(x1,xi,0,…,0︸m-2)≼⋯≼f(x1,x2,xi,…,xm-1,0)≼f(x1,x2,…,xm).
Hence,
(59)xi≼f(x1,x2,…,xm),
for all 1≤i≤m.
(ii) As(60)y1≼1,
by g operation on both sides of (60) with yj, we get
(61)g(y1,yj,1,…,1︸n-2)≼yj.
Similarly, we obtain
(62)g(y1,y2,…,yn)≼g(y1,y2,yj,…,yn-1,1)≼⋯≼g(y1,yj,1,…,1︸n-2)≼yj.
Hence,
(63)g(y1,y2,…,yn)≼yj,
for all 1≤j≤n.Corollary 30.
If≼ is a fault-tolerance partial order, then the following hold for all disjoint components xi,yj which are elements of 𝒰, where 1≤i≤m, 1≤j≤n and k,t∈ℤ+:(i)
f(x1,x2,…,xk,0,…,0︸m-k)≼f(x1m), where k<m,(ii)
g(y1n)≼g(y1,y2,…,yt,1,…,1︸n-t), where t<n.Proof.
(i) From (58), we deduce that
(64)f(x1,…,xk,0,…,0︸m-k)≼f(x1,…,xk+1,0,…,0︸m-k-1)≼⋯≼f(x1,x2,…,xm).
Therefore,
(65)f(x1,…,xk,0,…,0︸m-k)≼f(x1m).
(ii) As in part (i), we deduce from (62) that
(66)g(y1n)≼g(y1,y2,…,yt,1,…,1︸n-t).f
(
f
(
a
1
m
)
(
m
)
) represents the system which is obtained after applying the f operation on m repeated f(a1m) systems or subsystems. Similarly, g(g(b1n)(n)) represents the system which is obtained after applying the g operation on n repeated g(b1n) systems or subsystems.Theorem 31.
If≼ is a fault-tolerance partial order, and components x1,x2,…,xm, y1,y2,…,yn are disjoint components and are in 𝒰, then(i)
f(x1m)≼f(f(x1m)(m)),(ii)
g(g(y1n)(n))≼g(y1n).Corollary 32.
The following hold for all disjoint componentsx1,…,xm, z1,…,zn, y1,…,ym, u1,…,un, which are elements of 𝒰, where m,n∈ℤ+.(i)
Iff(f(x1m)(m))≼f(y1m), then
(67)f(x1m)≼f(y1m).(ii)
Ifg(z1n)≼g(g(u1n)(n)), then
(68)g(z1n)≼g(u1n).Proof.
(i)f(f(x1m)(m))≼f(y1m) and from Theorem 31, f(x1m)≼f(f(x1m)(m)). Therefore, f(x1m)≼f(y1m).
(ii) The proof is very similar to that of part (i).Corollary 33.
Letk and t be positive integers and k<m, t<n. Given disjoint components x1,…,xm, y1,y2,…,ym, z1,z2,…,zn, u1,u2,…,un that are in 𝒰, the following hold:(i)
Iff(0,…,0︸m-k,f(x1m)(k))≼f(y1m), then f(x1m)≼f(y1m).(ii)
Ifg(z1n)≼g(1,…,1︸n-t,g(u1n)(t)), then g(z1n)≼g(u1n).Proof.
Similar to Corollary32.Theorem 34.
Let≼ be a fault-tolerance partial order and xi≼yi and zj≼uj for all xi,yi,zj,uj∈𝒰, where 1≤i≤m and 1≤j≤n. Then, the following obtain:(i)
f(f(x1m)(m))≼f(f(y1m)(m)),(ii)
g(g(z1n)(n))≼g(g(u1n)(n)),(iii)
f(g(z1n)(m))≼f(g(u1n)(m)),(iv)
g(f(x1m)(n))≼g(f(y1m)(n)).Proof.
(i) As(69)xi≼yi,1≤i≤m,
from Lemma 27 (i), we get
(70)f(x1m)≼f(y1m).
This is written as
(71)f(0,…,0︸m-1,f(x1m))≼f(0,…,0︸m-1,f(y1m)).
So by f operation on both sides of (71) with f(x1m), we get
(72)f(f(0,…,0︸m-1,f(x1m)),f(x1m),0,…,0︸m-2)≼f(f(0,…,0︸m-1,f(x1m)),f(y1m),0,…,0︸m-2).
So by f operation on both sides of (71) with f(y1m), we get
(73)f(f(0,…,0︸m-1,f(x1m)),f(y1m),0,…,0︸m-2)≼f(f(0,…,0︸m-1,f(y1m)),0,…,0︸m-2,f(y1m)).
From (72) and (73), we get
(74)f(0,…,0︸m-2,f(x1m))(2)≼f(0,…,0︸m-2,f(y1m))(2).
Similarly, we get for m terms
(75)f(f(x1m))(m)≼f(f(y1m))(m).
(ii) We know that(76)zj≼uj,1≤j≤n.
From Lemma 27 (ii), we get
(77)g(z1n)≼g(u1n).
Which is represented as follows
(78)g(1,…,1︸n-1,g(z1n))≼g(1,…,1︸n-1,g(u1n)).
Now by g operation on both sides of (78) with g(z1n), we get
(79)g(g(z1n)(2),1,…,1︸n-2)≼g(g(z1n),g(u1n),1,…,1︸n-2).
So by g operation on both sides of (78) with g(u1n), we get
(80)g(1,…,1︸n-2,g(z1n),g(u1n))≼g(1,…,1︸n-2,g(u1n))(2).
So now from (79) and (80), we get
(81)g(1,…,1︸n-2,g(z1n))(2)≼g(1,…,1︸n-2,f(u1n))(2).
Similarly, we find for n terms
(82)g(g(z1n))(n)≼g(g(u1n))(n).
(iii) From Lemma27 (ii)
(83)g(z1n)≼g(u1n).
Similar to part (i), we find f operation of m terms and get
(84)f(g(z1n),g(z1n),…,g(z1n)︸m)≼f(g(u1n),g(u1n),…,g(u1n)︸m),f(g(z1n))(m)≼f(g(u1n))(m).
(iv) We know that(85)xi≼yi,1≤i≤m,
so from Lemma 27 (i), we get
(86)f(x1m)≼f(y1m).
As proved in part (ii), we find g operations of n terms and get
(87)g(f(x1m),f(x1m),…,f(x1m)︸n)≼g(f(y1m),f(y1m),…,f(y1m)︸n).
Thus, we get
(88)g(f(x1m))(n)≼g(f(y1m))(n).Corollary 35.
If≼ is a fault-tolerance partial order and k<m, t<n where k,t∈ℤ+, if xi≼yi, zj≼uj for all disjoint components xi, zj, yi, uj, which are in 𝒰, where 1≤i≤m and 1≤j≤n, then(i)
f(0,…,0︸m-k,f(x1m)(k))≼f(0,…,0︸m-k,f(y1m)(k)),(ii)
g(1,…,1︸n-tg(z1n)(t))≼g(1,…,1︸n-t,g(u1n)(t)).Proof.
(i) Proof is similar to that of Theorem34 (i). We find the f operation of k terms where ∀k∈ℤ+, and k<m.
(ii) Proof is similar to that of Theorem34 (ii). We find the g operation of t terms where ∀t∈ℤ+, and t<n.We propose the following theorem for very complex systems.Theorem 36.
If≼ is a fault-tolerance partial order, disjoint components ai, bi, cj, dj, xk, yk, zt, ut are in 𝒰 and ai≼bi, cj≼dj, xk≼yk and zt≼ut, where 1≤i≤m, 1≤j≤n, 1≤k≤m and 1≤t≤n, then(i)
f(x1k-1,f(a1m),xk+1m)≼f(y1k-1,f(b1m),yk+1m), for all 1≤k≤m;(ii)
f(x1k-1,g(c1n),xk+1m)≼f(y1k-1,g(d1n),yk+1m), for all 1≤k≤m;(iii)
g(z1t-1,f(a1m),zt+1n)≼g(u1t-1,f(b1m),ut+1n), for all 1≤t≤n; and(iv)
g(z1t-1,g(c1n),zt+1n)≼g(u1t-1,g(d1n),ut+1n), for all 1≤t≤n.Proof.
(i) From Lemma27 (i), if ai≼bi, then f(a1m)≼f(b1m) for all 1≤i≤m.
We prove in a similar manner as Lemma27 (i) that
(89)f(f(a1m),x1,0,…,0︸m-2)≼f(f(b1m),y1,0,…,0︸m-2).
Similarly, we get
(90)f(f(a1m),x1k-1,xk+1m)≼f(f(b1m),y1k-1,yk+1m).
Thus,
(91)f(x1k-1,f(a1m),xk+1m)≼f(y1k-1,f(b1m),yk+1m).
Similar to the above, we can prove (ii), (iii), and (iv).



---

*Source: 482391-2013-03-18.xml*