Strong Tolerance and Strong Universality of Interval Eigenvectors in a Max-Łukasiewicz Algebra

Abstract

The Łukasiewicz conjunction (sometimes also considered to be a logic of absolute comparison), which is used in multivalued logic and in fuzzy set theory, is one of the most important t-norms. In combination with the binary operation ‘maximum’, the Łukasiewicz t-norm forms the basis for the so-called max-Łuk algebra, with applications to the investigation of systems working in discrete steps (discrete events systems; DES, in short). Similar algebras describing the work of DES’s are based on other pairs of operations, such as max-min algebra, max-plus algebra, or max-T algebra (with a given t-norm, T). The investigation of the steady states in a DES leads to the study of the eigenvectors of the transition matrix in the corresponding max-algebra. In real systems, the input values are usually taken to be in some interval. Various types of interval eigenvectors of interval matrices in max-min and max-plus algebras have been described. This paper is oriented to the investigation of strong, strongly tolerable, and strongly universal interval eigenvectors in a max-Łuk algebra. The main method used in this paper is based on max-Ł linear combinations of matrices and vectors. Necessary and sufficient conditions for the recognition of strong, strongly tolerable, and strongly universal eigenvectors have been found. The theoretical results are illustrated by numerical examples.

1. Introduction A max-Łukasiewicz algebra (max-Łuk algebra, in short), is one of the so-called max-T fuzzy algebras, which are defined for various triangular norms.

A max-T fuzzy algebra contains values in the unit intervalI=⟨0,1⟩and uses the binary operation of maximum and one of the triangular norms, T, instead of the conventional operations of addition and multiplication. Thus, by a max-T fuzzy algebra we understand a triplet(I,⊕,_⊗T), whereIis the interval⟨0,1⟩and⊕=max,_⊗T=Tare binary operations onI. The symbolI(m,n), respectively,I(n), denotes the set of all matrices (respectively, vectors) of the given dimensions overI. The operations⊕,_⊗Tare extended to matrices and vectors in the standard way. The linear ordering onIinduces partial orderings onI(m,n)andI(n).

The triangular norms (t-norms, in short) were introduced in [1], in the context of probabilistic metric spaces. The t-norms are interpreted as the conjunction in multi-valued fuzzy logics, or as the intersection of fuzzy sets. These functions are used in many fields, such as statistics and game theory, information and data fusion, decision making support, risk management, and probability theory. The t-norms (and the corresponding t-conorms) play an important role in fuzzy set theory. Many t-norms can be found in [2]).

The Łukasiewicz norm is often considered to be a logic of absolute (or metric) comparison. The Łukasiewicz conjunction is defined by

x_⊗Ly=max{x+y−1,0}.

The simplest norm is the Gödel norm, and the conjunction is defined as the minimum of the entries: the truth degrees of the constituents. Gödel logic is considered to be a logic of relative comparison.

x_⊗Gy=min(x,y)

In the particular case whenT=min is the Gödel t-norm, we get an important max-min algebra which has useful applications to optimization and scheduling problems. Max-min algebras belong to the so-called tropical mathematics, with a wide scope of applications and interesting contributions to mathematical theory. Several monographs [3,4,5,6] and collections of papers [7,8,9,10,11,12,13] have dealt with tropical mathematics and related problems.

Tropical algebras can be naturally used for the study of systems working in discrete time (DES). The state of the system at time t is described by a vectorx(t). The transitions of the system from one state to another are described by the transition matrix A. The next statex(t+1)is obtained by multiplying the transition matrix and the state vector; in matrix notation we writeA⊗x(t)=x(t+1). When a DES reaches a steady state, after some time of operation, then the state vectors of the steady states are eigenvectors of A. In any tropical algebra, the eigenproblem for a given matrixA∈I(n,n)consists of finding an eigenvalueλ∈Iand an eigenvectorx∈I(n)fulfillingA⊗x=λ⊗x.

The eigenproblem in tropical algebra has been described in many papers, see [14]. Interesting results describing the structure of the eigenspace and several algorithms for computing the largest eigenvector of a given matrix have been published, for example, in [15,16]. The eigenvectors in a max-T algebra, for various triangular norms T, are useful in fuzzy set theory. Such eigenvectors have been studied in [17,18,19]. The eigenvalues and eigenvectors are interesting characteristics of the DES in fuzzy algebras. The eigenspace structures for the drastic and t-norm have been studied in [18,19]. Finally, [17] describes the case of Łukasiewicz fuzzy algebra.

2. Strong Types of Interval Eigenvectors in max-Łuk Algebras The investigation in this paper will be started by a simple numerical example.

Example 1.(Numerical illustration: Steady state vector).

Assume

A=0.50.40.10.10.50.80.80.20.10.70.60.60.60.200.40.50.50.20.40.30.10.400.8,x=0.50.70.50.40.8,λ=0.8.

Then

A_⊗Lx=0.30.50.30.20.6=0.8_⊗Lx.

That is, x is a max-Łuk eigenvector of A with the eigenvalueλ=0.8.

In practical applications, the matrix entries usually are not exact numbers, but are contained in some intervals. Interval arithmetic is an efficient way to represent matrix operations on a computer. Similarly, matrices and vectors with interval coefficients are studied in a max-Łuk algebra (or a max-min algebra, or some other tropical algebra), see [9,17,20,21,22,23]. The classification of various types of the interval eigenvectors in a max-min algebra has been investigated in [24,25].

Let n be a given natural number. We defineN={1,2,⋯,n} . Similarly to [21,25,26,27], we define the interval matrix with boundsA̲,A¯∈I(n,n)and the interval vector with boundsx̲,x¯∈I(n)as

[A̲,A¯]=A∈I(n,n);A̲≤A≤A¯,[x̲,x¯]=x∈I(n);x̲≤x≤x¯.

Let us assume that an interval matrixA=[A̲,A¯]and an interval vectorX=[x̲,x¯]have been fixed. The interval max-Łuk eigenproblem forAandXaims at recognizing whetherA_⊗Lx=λ_⊗Lxholds true forA∈A,x∈X,λ∈I, with suitable quantifiers (e.g., for allA∈A, for someA∈A, for allx∈X, for somex∈X ) and their various combinations. Various types of interval max-Łuk eigenvectors are defined, using various choices of quantifiers and their order (see [25] for the further classification types).

Definition 1.

Assume that an interval matrixAand an interval vectorXare given. Then,Xis called:

• A strong max-Łuk eigenvector ofA

  if(∃λ∈I)(∀A∈A)(∀x∈X)[A_⊗Lx=λ_⊗Lx];

• A strongly tolerable max-Łuk eigenvector ofA

  if(∃λ∈I)(∃A∈A)(∀x∈X)[A_⊗Lx=λ_⊗Lx];

• A strongly universal max-Łuk eigenvector ofA

  if(∃λ∈I)(∃x∈X)(∀A∈A)[A_⊗Lx=λ_⊗Lx].

Remark 1.

In general, an interval vectorXis called a tolerable max-Łuk eigenvector ofAif there is an eigenvalueλ∈Isuch that everyx∈Xpreserves the state vector up to a multiple by λ, for someA∈A(in other words: A tolerates x with eigenvalue λ).

In the case when there is one common tolerating matrixA∈Afor all of the vectorsx∈X, the interval vectorXis called strongly tolerable. Otherwise, the tolerating matrix A depends on x. If also the eigenvalue λ depends on x, then the interval eigenvectorXis usually called weakly tolerable.

Remark 2.

Similarly, an interval vectorXis called a universal max-Łuk eigenvector ofAif there is an eigenvalueλ∈Isuch that for everyA∈A, somex∈Xpreserves the state vector up to a multiple by λ, (in other words: x is universal for A with eigenvalue λ).

In the case when there is one common universal vectorx∈Xfor all matricesA∈A, the interval vectorX, as well as the common universal x, are called strongly universal. Otherwise, the universal vector x depends on A. If also the eigenvalue λ depends on A, then the interval eigenvectorXis usually called weakly universal.

In this paper, we study in more detail the strong max-Łuk interval eigenvectors, the strongly tolerable and strongly universal max-Łuk interval eigenvectors (the remaining types of max-Łuk interval eigenvector are not considered here). Necessary and sufficient conditions are described for recognizing whether a given interval vector is a strong (strongly tolerable, strongly universal) eigenvector of a given interval matrix in a max-Łuk algebra. The results are illustrated by numerical examples. 3. Strong Interval Eigenvectors in a max-Łuk Algebra

In this section, we assume that an interval matrixA=[A̲,A¯]and an interval vectorX=[x̲,x¯]are given. For each pairi,j∈N, define^A˜(ij)∈I(n,n)and^x˜(i)∈I(n)by putting for everyk,l∈N,

_a˜kl(ij)=_a¯ij,fork=i,l=j_a̲kl,otherwise,_x˜k(i)=_x¯i,fork=i_x̲k,otherwise.

It is shown in the following lemma that everyA∈Acan be written as a max-Łuk linear combination of generators^A˜(ij)withi,j∈N. Similarly, everyx∈Xis equal to a max-Łuk linear combination of generators^x˜(i)withi∈N.

Lemma 1.

Letx∈I(n)andA∈I(n,n). Then,

(i)

x∈Xif and only ifx=⨁i∈N_{βi ⊗L} ^x˜(i)for some_βi∈Iwith_x̲i−_x¯i+1≤_βi≤1,

(ii)

A∈Aif and only ifA=⨁i,j∈N_{αij ⊗L} ^A˜(ij)for some_αij∈Iwith_a̲ij−_a¯ij+1≤_αij≤1.

Proof.

For the proof of statement (i), assume thatx∈X: that is,_x̲i≤_xi≤_x¯ifor everyi∈N. Put_βi=_xi−_x¯i+1for eachi∈N. It is easy to see that the_βi‘s satisfy the inequalities in assertion (i). Moreover, for everyj∈N

_{⨁i∈Nβi ⊗L ^x˜(i)j}=⨁i∈N_{(xi−x¯i+1)⊗L ^x˜(i)j}=(_xj−_x¯j+1)_{⊗L x˜j(j)}⊕⨁i∈N∖{j}(_xi−_x¯i+1)_{⊗L x˜j(i)}=(_xj−_x¯j+1)_{⊗L x¯j}⊕⨁i∈N∖{j}(_xi−_x¯i+1)_{⊗L x̲j}.

In particular,(_xj−_x¯j+1)_{⊗L x¯j}=(_xj−_x¯j+1)+_x¯j−1=_xj, since_xj≥0. On the other hand, fori≠jwe have(_xi−_x¯i+1)_{⊗L x̲j}=(_xi−_x¯i+1)+_x̲j−1≤_xj, because_xi−_x¯i≤0.

For the converse implication, assume that_x̲i−_x¯i+1≤_βi≤1for everyi∈Nandx=⨁i∈N_{βi ⊗L} ^x˜(i). For everyj∈N

_xj=_{⨁i∈Nβi ⊗L ^x˜(i)j}≤_{⨁i∈N1⊗L ^x˜(i)j}=⨁i∈N_x˜j(i)=_x¯j⊕⨁i∈N∖{j}_x̲j=_x¯j,

_xj=_{⨁i∈Nβi ⊗L ^x˜(i)j}≥⨁i∈N_{(x̲i−x¯i+1)⊗L ^x˜(i)j}=(_x̲j−_x¯j+1)+_x¯j−1⊕⨁i∈N∖{j}(_x̲i−_x¯i+1)+_x̲j−1≥_x̲j⊕⨁i∈N∖{j}(_x̲i−_x¯i+_x̲j)=_x̲j.

We have shown thatx̲≤x≤x¯. That is,x∈[x̲,x¯]. The proof of (ii) is analogous. □

Theorem 1.

The interval vectorX=[x̲,x¯]is a strong max-Łuk eigenvector of the interval matrixA=[A̲,A¯]if and only if there existsλ∈I,λ>0,such that for everyi∈N.

A̲_⊗L ^x˜(i)=λ_⊗L ^x˜(i),

A¯_⊗L ^x˜(i)=λ_⊗L ^x˜(i).

Proof.

Assume thatλ∈I fulfills conditions (6) and (7), and thatx∈Xis given. Then x is a max-Łuk linear combinationx=_{⨁i∈Nβi ⊗L} ^x˜(i)for some coefficients_βi∈I,i∈Nwith_x̲i−_x¯i+1≤_βi≤1 , according to Lemma 1(i). In view of (6) we get

A̲_⊗Lx=A̲_⊗L⨁i∈N_{βi ⊗L} ^x˜(i)=⨁i∈NA̲_{⊗L βi ⊗L} ^x˜(i)=⨁i∈N_{βi ⊗L}A̲_⊗L ^x˜(i)=⨁i∈N_{βi ⊗L}λ_⊗L ^x˜(i)=λ_⊗L⨁i∈N_{βi ⊗L} ^x˜(i)=λ_⊗Lx.

Using (7) we analogously get

A̲_⊗Lx=A¯_⊗L⨁i∈N_{βi ⊗L} ^x˜(i)=λ_⊗L⨁i∈N_{βi ⊗L} ^x˜(i)=λ_⊗Lx.

From (8) and (9) it easily follows that

λ_⊗Lx=A̲_⊗Lx≤A_⊗Lx≤A¯_⊗Lx=λ_⊗Lx,A_⊗Lx=λ_⊗Lx,

for everyA∈A. That is,Xis a strong max-Łuk eigenvector ofA. The converse implication is trivial. □

Example 2.(Numerical illustration: Strong max-Luk eigenvector)

Assume lower and upper bounds forA∈[A̲,A¯]and forx∈[x̲,x¯]

A̲=0.60.20.10.10.50.20.20.100.40.10.30.20.40.20.30.50.40.60.200.10.300.3,A¯=0.60.60.30.10.60.20.60.30.10.60.50.90.60.40.90.710.80.60.90.20.60.30.10.6

x̲=000.70.90,x¯=0.80.40.70.90.4.

Then

^x˜(1)=0.800.70.90,^x˜(2)=00.40.70.90,^x˜(3)=000.70.90,^x˜(4)=000.70.90,^x˜(5)=000.70.90.4.

The following equations hold forλ=0.6

A̲_⊗L ^x˜(1)=0.400.30.50=A¯_⊗L ^x˜(1)=0.6_⊗L ^x˜(1),

A̲_⊗L ^x˜(2)=000.30.50=A¯_⊗L ^x˜(2)=0.6_⊗L ^x˜(2),

A̲_⊗L ^x˜(3)=000.30.50=A¯_⊗L ^x˜(3)=0.6_⊗L ^x˜(3),

A̲_⊗L ^x˜(4)=000.30.50=A¯_⊗L ^x˜(4)=0.6_⊗L ^x˜(4),

A̲_⊗L ^x˜(5)=000.30.50=A¯_⊗L ^x˜(5)=0.6_⊗L ^x˜(5).

Hence,X=[x̲,x¯]is a strong max-Łuk eigenvector of A with the eigenvalueλ=0.6.

Theorem 1 leads to the following recognition problem: givenAandX, recognize whether there is, or is no valueλ∈I∖{0} such that (6) and (7) hold for everyk∈N. If the answer is positive, then find all (or at least one) such values.

Ifi,k∈N, then we write, for brevity,

_zik=_{A̲⊗L ^x˜(i)k},_zik′=_{A¯⊗L ^x˜(i)k}.

Furthermore, we write

^Z0=(i,k)∈N×N;_zik=0

^Z>=(i,k)∈N×N;_zik>0

I=0,min(i,k)∈N×N1−_x˜k(i)

Theorem 2.

The interval vectorX=[x̲,x¯]is a strong max-Łuk eigenvector of the interval matrixA=[A̲,A¯]if and only if

(i)

(∀(i,k)∈N×N)_zik=_zik′,

(ii)

(∀(i,k)∈^Z0)_x˜k(i)<1,

(iii)

(∀(i,k),(j,l)∈^Z>)_x˜k(i)−_zik=_x˜l(j)−_zjl<1,

(iv)

(∀(i,k)∈^Z>,(j,l)∈^Z0)_x˜l(j)≤_x˜k(i)−_zik.

Proof.

Assume thatXis a strong interval eigenvector ofA. That is, there existsλ∈I,λ>0 fulfilling conditions (6) and (7). The statement (i) then follows immediately. For(i,k)∈^Z0we have_zik=0, which givesλ_{⊗L x˜k(i)}=0 , in view of (6). Then, by definition of_⊗L, we haveλ+_x˜k(i)−1≤0, which impliesλ≤1−_x˜k(i). Now, statement (ii) easily follows, in view of the assumption that0<λ.

For(i,k),(j,l)∈^Z>, we have_zik>0, which givesλ_{⊗L x˜k(i)}>0 , in view of (6). Consequently,_zik=λ+_x˜k(i)−1. That is,λ=−_x˜k(i)+_zik+1. Similarly,λ=−_x˜l(j)+_zjl+1. In view of the assumption thatλ>0, we get (iii) by a simple computation. Finally, assume(i,k)∈^Z0,(j,l)∈^Z>. By the same arguments as above, we getλ=−_x˜k(i)+_zik+1≤1−_x˜l(j). Then (iv) follows directly.

For the converse implication, assume that statements (i)–(iv) hold. We shall show that then aλ>0 can be found such that (6) and (7) are satisfied. We distinguish two cases.

Case 1.^Z>=Ø. Then^Z0=N×N, and by (ii) we have0<1−_x˜k(i)for every(i,k)∈N×N. That is, the interval I is non-empty. Choose an arbitraryλ∈I. Then, for every(i,k)∈N×N, we haveλ≤1−_x˜k(i)which givesλ+_x˜k(i)−1≤0. That is,λ_{⊗L x˜k(i)}=0=_zik. As(i,k) is arbitrary, (6) has been demonstrated. Then, (7) follows by statement (i).

Case 2.^Z>≠Ø. Let(i,k)∈^Z>be fixed. By (iii) we have_x˜k(i)−_zik<1, which gives0<_zik+1−_x˜k(i). Choosingλ=_zik+1−_x˜k(i), we getλ>0and_zik=λ+_x˜k(i)−1. Then, the assumption that(i,k)∈^Z>implies_zik>0andλ+_x˜k(i)−1>0. That is,λ+_x˜k(i)−1=λ_{⊗L x˜k(i)}, which implies_zik=λ_{⊗L x˜k(i)}.

Consider an arbitrary(j,l)∈^Z>. We haveλ=_zik+1−_x˜k(i)=_zjl+1−_x˜l(j), in view of (iii). That is,_zjl=λ_{⊗L x˜l(j)}, similarly as above. On the other hand, for every(j,l)∈^Z0we have_x˜l(j)≤_x˜k(i)−_zik, in view of (iv). Consequently, we get_zik+1−_x˜k(i)≤1−_x˜l(j). That is,λ≤1−_x˜l(j), which givesλ+_x˜l(j)−1≤0. This impliesλ_{⊗L x˜l(j)}=0, i.e.,_zjl=λ_{⊗L x˜l(j)}.As(j,l)∈^Z>∪^Z0=N×N was arbitrary, we have shown that (6) is satisfied. By (i), (7) holds as well. □

Remark 3.

The proof of Theorem 2 contains a description of the setS(A,X)=λ>0;(∀A∈A)(∀x∈X)A_⊗Lx=λ_⊗Lx.Namely

• if some of statements (i)–(iv) in Theorem 2 are not satisfied, thenS(A,X)=Ø,

• if(i,k)∈^Z>, thenS(A,X)=λ=_zik+1−_x˜k(i),

• if^Z>=Ø, thenS(A,X)=0,mini,k∈N1−_x˜k(i).

Theorem 3.

The recognition problem of whether a given interval vectorXis a strong max-Łuk eigenvector of the interval matrixAis solvable inO(ⁿ³)time.

Proof.

According to Theorem 2, the problem can be solved by verifying conditions (i)–(iv). Each of them can be verified inOⁿ³time. Therefore, the computational complexity isOⁿ³.□

4. Strongly Tolerable Interval Eigenvectors in a max-Łuk Algebra

Theorem 4.

The interval vectorX=[x̲,x¯]is a strongly tolerable max-Łuk eigenvector of the interval matrixA=[A̲,A¯]if and only if there exist anA∈Aandλ∈Isuch that

A_⊗L ^x˜(k)=λ_⊗L ^x˜(k)for every k∈N.

Proof.

Let us assume thatA∈Aandλ∈I fulfill condition (15). Ifx∈I(n)is an arbitrary vector inX, then x is a max-Łuk linear combinationx=_{⨁k∈Nβk ⊗L} ^x˜(k)for some coefficients_βk∈I,k∈Nwith_x̲k−_x¯k+1≤_βi≤1. According to Lemma 1 (i),

A_⊗Lx=A_⊗L⨁k∈N_{βk ⊗L} ^x˜(k)=⨁k∈NA_{⊗L βk ⊗L} ^x˜(k)=⨁k∈N_{βk ⊗L}A_⊗L ^x˜(k)=⨁k∈N_{βk ⊗L}λ_⊗L ^x˜(k)=λ_⊗L⨁k∈N_{βk ⊗L} ^x˜(k)=λ_⊗Lx.

By (3),Xis a strongly tolerable eigenvector ofA. The converse implication follows immediately. □

Remark 4.

The property (15) can be briefly expressed in words: A is aλ-certificate for the strong tolerance max-Łuk problem(A,X).

Example 3.(Numerical illustration: Strongly tolerable max-Luk eigenvector)

Assume the lower and upper bounds forA∈[A̲,A¯]and forx∈[x̲,x¯]are

A̲=0.20.20.20.300.10.30.20.3000.10.20.30.10.10.20.10.20.20.10.10.20.10.4,A¯=0.80.80.90.70.50.50.80.90.80.50.50.70.50.50.80.50.50.50.80.80.50.20.90.90.8

x̲=0.600.600.7,x¯=0.80.70.60.40.7.

Then

^x˜(1)=0.800.600.7,^x˜(2)=0.60.70.600.7,^x˜(3)=0.600.600.7,^x˜(4)=0.600.60.40.7,^x˜(5)=0.600.600.7.

Forλ=0.7and for given_A1∈A

_A1=0.70.60.70.60.10.20.70.40.60.10.20.20.30.40.60.20.30.40.70.30.20.10.80.80.4

the following equations hold

_{A1 ⊗L} ^x˜(1)=0.70.60.70.60.10.20.70.40.60.10.20.20.30.40.60.20.30.40.70.30.20.10.80.80.4⊗0.800.600.7=0.500.300.4=0.7_⊗L ^x˜(1),

_{A1 ⊗L} ^x˜(2)=0.70.60.70.60.10.20.70.40.60.10.20.20.30.40.60.20.30.40.70.30.20.10.80.80.4⊗0.60.70.600.7=0.30.40.300.4=0.7_⊗L ^x˜(2),

_{A1 ⊗L} ^x˜(3)=0.70.60.70.60.10.20.70.40.60.10.20.20.30.40.60.20.30.40.70.30.20.10.80.80.4⊗0.600.600.7=0.300.300.4=0.7_⊗L ^x˜(3),

_{A1 ⊗L} ^x˜(4)=0.70.60.70.60.10.20.70.40.60.10.20.20.30.40.60.20.30.40.70.30.20.10.80.80.4⊗0.600.60.40.7=0.300.30.10.4=0.7_⊗L ^x˜(4),

_{A1 ⊗L} ^x˜(5)=0.70.60.70.60.10.20.70.40.60.10.20.20.30.40.60.20.30.40.70.30.20.10.80.80.4⊗0.600.600.7=0.300.300.4=0.7_⊗L ^x˜(5),

Hence,X=[x̲,x¯]is a strongly tolerable max-Łuk eigenvector ofAwith the eigenvalueλ=0.7, and_A1is the λ-certificate for the strong tolerance max-Łuk problem(A,X).

Remark 5.

In general, not every matrixA∈Ais a λ-certificate for(A,X), for some λ. Take, e.g.,

_A2=0.80.80.90.70.50.50.80.90.80.50.50.70.50.50.80.50.50.50.80.80.50.20.90.90.8

and^x˜(1),^x˜(2),^x˜(3),^x˜(4),^x˜(5)from Example 3. Then

_{A2 ⊗L} ^x˜(1)=_A2⊗0.800.600.7=00000.1≠λ_⊗L ^x˜(1).

It is easy to see that the equality in the last position cannot hold for anyλ∈I. That is,_A2is not a λ-certificate in Example 3 with anyλ∈I.

In Example 3, the certificate_A1was given. Now the question arises of how to find a certificate (or to show that no certificate exists) for a given instance(A,X). In other words, how do we recognize whether or notXis a strongly tolerable interval eigenvector ofA?

A method for solving the strong tolerance interval eigenproblem in a max-Łuk algebra for instances with a natural additional condition is described in the rest of this section. We start with a simple lemma.

Lemma 2.

Assumeu,v,w∈I.

(i)

Ifu+v+w>2, then(u_⊗Lv)_⊗Lw=u+v+w−2>0,

(ii)

Ifu+v+w≤2, then(u_⊗Lv)_⊗Lw=0.

Proof.

Letu+v+w>2. Thenu+v>2−w≥2−1=1, since0≤w≤1. Hence,u_⊗Lv=u+v−1>0, and(u_⊗Lv)_⊗Lw=(u+v−1)+w−1=u+v+w−2>0.

On the other hand, ifu+v+w≤2, then(u+v−1)+(w−1)≤0. We consider two subcases.

Subcase 1. Supposeu+v−1>0. Thenu_⊗Lv=u+v−1andu_⊗Lv+w−1≤0. Hence,(u_⊗Lv)_⊗Lw=0.

Subcase 2. Supposeu+v−1≤0. Thenu_⊗Lv=0andu_⊗Lv+w−1=0+w−1≤0, sincew≤1. That is,(u_⊗Lv)_⊗Lw=0. □

Remark 6.

It is easy to see directly from the definition that the Łukasiewicz conjunction_⊗Lis commutative. As a consequence of Lemma 2,_⊗Lis associative, as well.

Namely due to Lemma 2(i), we have, for anyu,v,w∈Iwithu+v+w>2, that(u_⊗Lv)_⊗Lw=u+v+w−2, and, by the commutative law,u_⊗L(v_⊗Lw)=(v_⊗Lw)_⊗Lu=v+w+u−2. That is,(u_⊗Lv)_⊗Lw=u_⊗L(v_⊗Lw). Similar reasoning is used whenu+v+w≤2.

To recognize the existence of a certificateA∈A satisfying the conditions (15) from Theorem 4, the unknown A will be written as a max-Łuk linear combination of generators^A˜(ij)as in Lemma 1 (ii).

The coefficients in the linear combination will be found as the solution to a system of max-Łuk linear equations with parameterλ, and the variables_α(ij)in the bounds_a̲ij=_α̲(ij)≤_α(ij)≤_α¯(ij)=_a¯ij. The form of the system will require that every solution of the system, for some parameter valueλ, gives coefficients for such a max-Łuk linear combination of generators which is aλ-certificate matrix for the given instance. Then the recognition of strong tolerability is equivalent to the recognition of whether there is a valueλfor which the system is solvable. On the other hand, if the system is unsolvable for everyλ∈I, then no certificate exists for the given instance.

Formally, we consider the bounded max-Łuk linear system

C˜_⊗Lα=λ_⊗Lb˜

α̲≤α≤α¯

with parameterλ∈I, where the columns^C˜(ij)ofC˜∈I(ⁿ²,ⁿ²)are constructed blockwise from^A˜(ij)⊗^x˜(k),k∈N. The right-hand side vectorb˜∈I(ⁿ²)is constructed blockwise from the generators^x˜(k)fork∈N, and the boundsα̲,α¯∈I(ⁿ²)for the variable vectorα∈I(ⁿ²)are constructed from the columns ofA̲,A¯, according to Lemma 1 (ii). That is, we have

^C˜(ij)=^A˜(ij) _⊗L ^{x˜(1)A˜(ij)} _⊗L ^x˜(2)⋮^A˜(ij) _⊗L ^x˜(n),b˜=^x˜(1)x˜(2)⋮^x˜(n),

_α̲(ij)=_a̲ij−_a¯ij+1≤_α(ij)≤1=_α¯(ij).

Theorem 5.

The interval vectorX=[x̲,x¯]is a strongly tolerable eigenvector of the interval matrixA=[A̲,A¯]if and only if there is aλ∈I such that the linear system (17) and (18), has a solutionα∈I(ⁿ²). In the positive case, the max-Łuk linear combination

A=⨁(ij)∈N×N_{α(ij) ⊗L} ^A˜(ij)

is a λ-certificate for the given instance.

Proof.

Assume that there exists aλ∈Isuch thatα satisfies (17), (18) with (19), (20). Then,A∈I(n,n) as defined in (21) belongs to[A̲,A¯], in view of Lemma 1(ii). Moreover, we have the following block equations, for everyk∈N

⨁i,j∈N^A˜(ij) _⊗L ^x˜(k)_{⊗L α(ij)}=λ_⊗L ^x˜(k),

⨁i,j∈N_{α(ij) ⊗L} ^A˜(ij)_⊗L ^x˜(k)=λ_⊗L ^x˜(k),

A_⊗L ^x˜(k)=λ_⊗L ^x˜(k).

We will prove that the block Equations (22) and (23) are equivalent. In particular, we show that the left-hand sides of (22) and (23) in every row h and in every block row k are equal.

Assumek,h∈Nare fixed. Then

_{⨁i,j∈N^A˜(ij) ⊗L ^x˜(k)⊗L α(ij)h}=⨁i,j∈N_{^A˜(ij) ⊗L ^x˜(k)h ⊗L α(ij)}

=⨁i,j∈N⨁g∈N_{A˜hg(ij) ⊗L x˜g(k)⊗L α(ij)}=⨁i,j∈N⨁g∈N_{A˜hg(ij) ⊗L x˜g(k)⊗L α(ij)}

=⨁i,j∈N⨁g∈N_{α(ij) ⊗LA˜hg(ij) ⊗L x˜g(k)}=⨁i,j∈N⨁g∈N_{α(ij) ⊗L A˜hg(ij)⊗L x˜g(k)}

=⨁i,j∈N_{α(ij) ⊗L ^A˜(ij)h ⊗L} ^x˜(k)=_{⨁i,j∈Nα(ij) ⊗L ^A˜(ij)⊗L ^x˜(k)h}

Please note that the associative law has been used in (27). That is,

_{α(ij) ⊗LA˜hg(ij) ⊗L x˜g(k)}=_{α(ij) ⊗L A˜hg(ij)⊗L x˜g(k)},

according to Remark 6. The remaining equalities (25), (26) and (28) are consequences of standard arithmetic rules in max-Łuk algebras.

Now, in view of the fact that (22) means thatα∈I(ⁿ²) is a solution of (19), while (23) says that (21) satisfies (15), we obtain, due to Theorem 4 thatXis a strongly tolerable eigenvector ofA. The converse implication follows from the converse implication in Theorem 4. □

Theorem 5 reduces the recognition problem of whetherXis a strongly tolerable eigenvector ofA to the solvability problem of the bounded parametric system (17), (18) with dimensionⁿ²×ⁿ²for someλ∈I. The latter problem is a particular case of the bounded parametric solvability problem with general dimensionm×n . The recognition algorithm can be briefly described by the following steps (for details and notation, see [28]):

(I)

permute the equations in the system so that the right-hand side will be decreasing, that is

0≤1−_b1≤1−_b2≤⋯≤1−_bm≤1,

(II)

recognize the solvability for someλwith1−_bm<λ≤1 , according to [28]/Theorem 3 (case a), by verifyingC_⊗L ^y★(_λmaxm)=_{λmaxm ⊗L}b,

(III)

recognize the solvability for someλwith0≤⋯≤1−_bh<λ≤1−_bh+1≤⋯1 , according to [28]/Theorem 4 (case b), by verifyingC_⊗L ^y★(_λmaxh)=_{λmaxh ⊗L}b. This step may be repeated, if necessary, with different indicesh≤m,

(iv)

recognize the solvability for someλwith0≤λ≤1−_b1 , according to [28]/Theorem 5 (case c), by verifying_y̲j≤_⋀i∈M1−_cij, for everyj∈N.

(v)

the system is solvable if the answer is positive at least once in steps 2, 3 or 4. Otherwise, the system is unsolvable for any value ofλ.

Theorem 6.

The recognition problem of whether a given interval vectorXis a strongly tolerable eigenvector of a given interval matrixAin a max-Łuk algebra is solvable inO(ⁿ⁶)time.

Proof.

According to [28], the parametric solvability problem with dimensionm×nhas the computational complexityO(mⁿ²). Therefore, the computational complexity of the strong tolerance problem with dimensionⁿ²×ⁿ²isO⁽ⁿ²⁾³=O(ⁿ⁶). □

Example 4.(Numerical illustration: Computing a certificate)

Assume that the lower and upper bounds forA∈[A̲,A¯]andx∈[x̲,x¯]in the interval eigenproblem are

A̲=0.90.70.60.70.90.60.80.80.9,A¯=10.80.80.70.90.810.91

x̲=0.70.80.9,x¯=0.90.80.9.

If we wish to recognize whetherXis a strongly tolerable max-Łuk eigenvector ofA, then, according to Theorem 4, we must recognize the existence of a λ-certificate for(A,X). In view of Theorem 5, we must recognize the solvability of the max-Łuk linear systemC˜_⊗Lα=λ_⊗Lb˜with boundsα̲≤α≤α¯, for someλ∈I. The vector (matrix) generators are

^x˜(1)=0.90.80.9,^x˜(2)=0.70.80.9,^x˜(3)=0.70.80.9.

^A˜(11)=10.70.60.70.90.60.80.80.9,^A˜(12)=0.90.80.60.70.90.60.80.80.9,

^A˜(13)=0.90.70.80.70.90.60.80.80.9,^A˜(21)=0.90.70.60.70.90.60.80.80.9,

^A˜(22)=0.90.70.60.70.90.60.80.80.9,^A˜(23)=0.90.70.60.70.90.80.80.80.9,

^A˜(31)=0.90.70.60.70.90.610.80.9,^A˜(32)=0.90.70.60.70.90.60.80.90.9,

^A˜(33)=0.90.70.60.70.90.60.80.81.

The columns of the matrixC˜∈I(9,9)and the right-hand side vectorb˜∈I(9) are computed blockwise according to (19), as follows.

^C˜(11)=^A˜(11) _⊗L ^{x˜(1)A˜(11)} _⊗L ^{x˜(2)A˜(11)} _⊗L ^x˜(3)=0.90.70.80.70.70.80.70.70.8,^C˜(12)=^A˜(12) _⊗L ^{x˜(1)A˜(12)} _⊗L ^{x˜(2)A˜(12)} _⊗L ^x˜(3)=0.80.70.80.60.70.80.60.70.8,

^C˜(13)=^A˜(13) _⊗L ^{x˜(1)A˜(13)} _⊗L ^{x˜(2)A˜(13)} _⊗L ^x˜(3)=0.80.70.80.70.70.80.70.70.8,^C˜(21)=^A˜(21) _⊗L ^{x˜(1)A˜(21)} _⊗L ^{x˜(2)A˜(21)} _⊗L ^x˜(3)=0.80.70.80.60.70.80.60.70.8,

^C˜(22)=^A˜(22) _⊗L ^{x˜(1)A˜(22)} _⊗L ^{x˜(2)A˜(22)} _⊗L ^x˜(3)=0.80.70.80.60.70.80.60.70.8,^C˜(23)=^A˜(23) _⊗L ^{x˜(1)A˜(23)} _⊗L ^{x˜(2)A˜(23)} _⊗L ^x˜(3)=0.80.70.80.60.70.80.60.70.8,

^C˜(31)=^A˜(31) _⊗L ^{x˜(1)A˜(31)} _⊗L ^{x˜(2)A˜(31)} _⊗L ^x˜(3)=0.80.70.90.60.70.80.60.70.8,^C˜(32)=^A˜(32) _⊗L ^{x˜(1)A˜(32)} _⊗L ^{x˜(2)A˜(32)} _⊗L ^x˜(3)=0.80.70.80.60.70.80.60.70.8,

^C˜(33)=^A˜(33) _⊗L ^{x˜(1)A˜(33)} _⊗L ^{x˜(2)A˜(33)} _⊗L ^x˜(3)=0.80.70.90.60.70.90.60.70.9,b˜=^{x˜(1)x˜(2)x˜(3)}=0.90.80.90.70.80.90.70.80.9.

Hence, we wish to recognize the solvability of the system

C˜_⊗Lα=0.90.80.80.80.80.80.80.80.80.70.70.70.70.70.70.70.70.70.80.80.80.80.80.80.90.80.90.70.60.70.60.60.60.60.60.60.70.70.70.70.70.70.70.70.70.80.80.80.80.80.80.80.80.90.70.60.70.60.60.60.60.60.60.70.70.70.70.70.70.70.70.70.80.80.80.80.80.80.80.80.9_{⊗Lα1α2α3α4α5α6α7α8α9}=λ_⊗L0.90.80.90.70.80.90.70.80.9=λ_⊗Lb˜.

The problem is a particular case of the bounded parametric solvability problem, with dimensionⁿ²×ⁿ² , and can be solved by the algorithm suggested in [28] (see also a brief description in this paper, before Theorem 6).

Depending on the permuted entries ofb˜, we distinguish the following four cases: (a)λ∈(0.3,1⟩, (b)λ∈(0.1,0.2⟩,λ∈(0.2,0.3⟩and (c)λ∈(0,0.1⟩. We can verify that forλ=0.9the systemC˜_⊗Lα=λ_⊗Lb˜has a solutionα=^{(0.9,0.7,0.9,0.8,0.9,0.9,0.8,0.8,1)T}fulfilling the inequalities_a̲ij−_a¯ij+1≤_α(ij)≤1,for every(i,j)∈N×N.

Using the coefficients_α(ij)we get, by Theorem 5, thatXis a strongly tolerable eigenvector ofA, with certificate

A=⨁(ij)∈N×N_{α(ij) ⊗L} ^A˜(ij)=0.90.70.70.70.90.70.80.81.

Example 5.(Numerical illustration: Computing a certificate - no certificate exists)

We assume the same lower and upper bounds forA∈[A̲,A¯]as in Example 4 and take different bounds forx∈[x̲,x¯].

A̲=0.90.70.60.70.90.60.80.80.9,A¯=10.80.80.70.90.810.91,

x̲=0.70.70.7,x¯=111.

Then the generators of A stay the same and

^x˜(1)=10.70.7,^x˜(2)=0.710.7,^x˜(3)=0.70.71.

The matrixC˜and the right-hand sideb˜then are

C˜=10.90.90.90.90.90.90.90.90.70.70.70.70.70.70.70.70.70.80.80.80.80.80.810.80.80.70.80.70.70.70.70.70.70.70.90.90.90.90.90.90.90.90.90.80.80.80.80.80.80.80.90.80.70.60.80.60.60.60.60.60.60.60.60.60.60.60.80.60.60.60.90.90.90.90.90.90.90.91,b˜=10.70.70.710.70.70.71.

Similarly as in the previous example we distinguish, depending on the permuted entries ofb˜, the following three cases: (a)λ∈(0.3,1⟩, (b)λ∈(0,0.3⟩and (c)λ=0. It can be verified that the systemC˜_⊗Lα=λ_⊗Lb˜has no solution in any of these cases.

Consequently, the considered system is not solvable for any value of λ. That is, no certificate for strong tolerability exists and the givenXis not a strongly tolerable eigenvector ofA.

5. Strongly Universal Interval Eigenvectors in a max-Łuk Algebra

In this section, we present two necessary and sufficient conditions for characterizing a strongly universal eigenvector. The first condition is based on the generators ofA, while the second one uses the lower bound and the upper bound ofA.

Theorem 7.

LetAandXbe given such that_a̲ij=_a¯ijfor somei,j∈N. The interval vectorXis a strongly universal max-Łuk eigenvector of the interval matrixA=[A̲,A¯]if and only if there exists anx∈Xand aλ∈Isuch that

^A˜(ij) _⊗Lx=λ_⊗Lxforevery i,j∈N.

Proof.

Let us assume that there arex∈Xandλ∈I fulfilling condition (30). IfA∈I(ⁿ²)is an arbitrary matrix inA, then A is a max-Łuk linear combinationA=_{⨁ij∈Nαij ⊗L} ^A˜(ij)for some coefficients_αij∈I,i,j∈Nwith_a̲ij−_a¯ij+1≤_αij≤1. According to Lemma 1(ii),

A_⊗Lx=⨁ij∈N_{αij ⊗L} ^A˜(ij)_⊗Lx=⨁ij∈N_{αij ⊗L}^A˜(ij) _⊗Lx=⨁ij∈N_{αij ⊗L}λ_⊗Lx=⨁ij∈N_{αij ⊗L}λ_⊗Lx=λ_⊗Lx

because_a̲ij=_a¯ijfor somei,j∈Nimplies_{⨁ij∈Nαij}=1and_{⨁ij∈Nαij ⊗L}λ=λ. By Definition 1,Xis a strongly universal eigenvector ofA. The converse implication follows immediately. □

Theorem 8.

Suppose given an interval matrixA=[A̲,A¯]and interval vectorXwith boundsx̲,x¯. ThenXis a strongly universal eigenvector ofAif and only if there areλ∈Iandx∈Xsuch thatA̲_⊗Lx=λ_⊗LxandA¯_⊗Lx=λ_⊗Lx.

Proof.

Let us suppose that there areλandx∈Xsuch thatA̲_⊗Lx=A¯⊗x=λ⊗x. From the monotonicity of the operations ⊕ and_⊗Lwe getλ_⊗Lx=A̲_⊗Lx≤A_⊗Lx≤A¯_⊗Lx=λ_⊗Lxfor everyA∈A. The converse implication is trivial. □

The condition described in Theorem 8 can be verified by solving a two-sided max-Łuk system defined as follows. Define the block matricesC∈I(2n,n),D∈I(2n,n)by

C=A̲_⊗L ^x˜(1)⋯A̲_⊗L ^x˜(n)A¯_⊗L ^x˜(1)⋯A¯_⊗L ^x˜(n),D=^x˜(1)⋯^x˜(n)x˜(1)⋯^x˜(n).

Theorem 9.

Assume that an interval matrixA=[A̲,A¯]and an interval vectorX=[x̲,x¯]are given. ThenXis a strongly universal eigenvector ofAif and only if the bounded two-sided max-Łuk linear system with variableβ∈I(n)

C_⊗Lβ=λ_⊗LD_⊗Lβ

x̲−x¯+1≤β≤1

is solvable for some value of the parameterλ∈I. Ifβ∈I(n)is a solution to the system, thenx=_{⨁i=1n βi}⊗^x˜isatisfies the condition in Theorem 8.

Proof.

Let us suppose that there is aλsuch that the two-sided systemC⊗β=λ⊗D⊗βhas a solutionβ. Putx=_{⨁i=1n βi}⊗^x˜i. Then the following formulas are equivalent

C⊗β=λ⊗D⊗β

⨁i=1nA̲⊗^x˜(i)⊗_βi=λ⊗⨁i=1n^x˜(i)⊗_βiand⨁i=1nA¯⊗^x˜(i)⊗_βi=λ⊗⨁i=1n^x˜(i)⊗_βi

⨁i=1nA̲⊗^x˜(i)⊗_βi=λ⊗⨁i=1n^x˜(i)⊗_βiand⨁i=1nA¯⊗^x˜(i)⊗_βi=λ⊗⨁i=1n^x˜(i)⊗_βi

A̲⊗⨁i=1n_βi⊗^x˜(i)=λ⊗⨁i=1n_βi⊗^x˜(i)andA¯⊗⨁i=1n_βi⊗^x˜(i)=λ⊗⨁i=1n_βi⊗^x˜(i)

A̲⊗x=λ⊗xandA¯⊗x=λ⊗x.

The assertion follows by Theorem 8. □

By Theorem 9, the verification of whetherXis a strongly universal eigenvector ofAis reduced to the verification of the solvability of the systemC_⊗Lx=λ_⊗LD_⊗Lx. A similar situation in max-min algebra is solved by a polynomial algorithm for the solvability of such a system, with a complexity equal toO(ⁿ³) [29].

In max-plus algebra, the solvability of the considered system has been generally shown to be polynomially equivalent to solving a mean-payoff game [30]. That is, there exist efficient pseudopolynomial algorithms for this problem. On the other hand, the existence of a polynomial algorithm is a long-standing open question. Similarly, for a max-Łuk algebra, the existence of a polynomial algorithm for the solvability recognition problem remains open.

Example 6.(Numerical illustration: Strongly universal interval eigenvector)

Assume thatA∈[A̲,A¯]andx∈[x̲,x¯]

A̲=0.60.30.40.100.20.20.20.6,A¯=0.60.70.50.40.60.50.50.70.6

x̲=0.10.20.1,x¯=0.70.60.7.

It is easy to verify that for a givenλ=0.4,x=^{(0.1,0.2,0.1)T}and for every matrix generator^A˜ij,i,j∈N,

^A˜ij⊗x=^A˜ij⊗0.10.20.1=000=0.4⊗0.10.20.1=λ_⊗Lx.

Hence, in view of Theorem 7, the interval vectorXis a strongly universal max-Łuk eigenvector of the interval matrixA.

Theorem 9 offers a more systematic approach: find a solution to the two-sided system (32) and (33) with unknown coefficients β, for some^λ′∈I:

0.300.1000000.30.30.30.20.10.20.20.20.30.3_{⊗Lβ1β2β3}=^λ′ _⊗L0.70.10.10.20.60.20.10.10.70.70.10.10.20.60.20.10.10.7_{⊗Lβ1β2β3},

0.40.60.4≤_β1β2β3≤111.

In this particular instance, it is easy to verify that^β′=^{(0.9,0.8,0.8)T}is a solution to the system with^λ′=0.6. Then the corresponding linear combination of generators,^x′=(0.9_⊗L ^x˜(1))⊕(0.8_⊗L ^x˜(2))⊕(0.8_⊗L ^x˜(3))=^{(0.6,0.4,0.5)T}, satisfies the condition from Theorem 8. It is worth noticing that we have found two different universal eigenvectors x and^x′for two different values λ and^λ′in this example. Hence, we have shown that neither the “strongly universal” eigenvalue nor the strongly universal eigenvector are uniquely determined.

6. Conclusions Strong versions of the notion of an interval eigenvector of an interval matrix in a max-Łuk algebra have been investigated in this paper. The steady states of a given discrete events system (DES) correspond to eigenvectors of the transition matrix of the system under consideration. When the entries of the state vectors and transition matrix are supposed to be contained in some intervals, then several types of interval eigenvector can be defined, according to the choice of the quantifiers used in the definition. Three of the main important types of interval eigenvectors of a given interval matrix in a max-Łuk algebra have been studied: the strong eigenvector, the strongly tolerable eigenvector, and the strongly universal eigenvector. Using vector generators and matrix generators belonging to given intervals, the structure of the eigenspace for each of the above mentioned types has been described, and necessary and sufficient conditions for the existence of an interval eigenvector have been formulated. Moreover, recognition algorithms have been suggested for the recognition of these conditions for the first two types: strong and strongly tolerable eigenvector. The existence of an efficient recognition algorithm for the strongly universal type has not been shown. This question remains as a challenge for future research. These results can be useful in practical applications aimed at the construction of real DES working with Łukasiewicz fuzzy logic. The results have been illustrated by numerical examples.

Author Contributions

Investigation, M.G., Z.N. and J.P.; Writing-review and editing, M.G., Z.N. and J.P. All authors contributed equally to this manuscript. All authors have read and agreed to the published version of the manuscript.

Funding

This research was funded by the Czech Science Foundation (GAČR) #18-01246S and by the Faculty of Informatics and Management UHK, specific research project 2107 Computer Networks for Cloud, Distributed Computing, and Internet of Things III.

Conflicts of Interest

The authors declare no conflict of interest. The funders had no role in the design of the study; in the collection, analyses, or interpretation of data; in the writing of the manuscript, or in the decision to publish the results.

References

1. Schweizer, B.; Sklar, A. Statistical metric spaces. Pac. J. Math. 1960, 10, 313-334.

2. Gottwald, S. A Treatise on Many-Valued Logics; Studies in Logic and Computation, Research Studies Press: Baldock, Great Britain, 2001.

3. Gavalec, M. Periodicity in Extremal Algebras; Gaudeamus: Hradec Králové, Czech Republic, 2004.

4. Golan, J.S. Semirings and Their Applications; Springer: Berlin, Germany, 2013.

5. Gondran, M.; Minoux, M. Graphs, Dioids and Semirings: New Models and Algorithms; Springer: Berlin, Germany, 2008; Volume 41.

6. Kolokoltsov, V.; Maslov, V.P. Idempotent Analysis and Its Applications; Springer: Berlin, Germany, 1997; Volume 401.

7. Mysková, H. Interval eigenvectors of circulant matrices in fuzzy algebra. Acta Electrotech. Inform. 2012, 12, 57.

8. Mysková, H. Weak stability of interval orbits of circulant matrices in fuzzy algebra. Acta Electrotech. Inform. 2012, 12, 51.

9. Plavka, J. On the weak robustness of fuzzy matrices. Kybernetika 2013, 49, 128-140.

10. Tan, Y.J. Eigenvalues and eigenvectors for matrices over distributive lattices. Linear Algebra Appl. 1998, 283, 257-272.

11. Zimmermann, K. Extremální Algebra; Útvar vědeckỳch Informací Ekonomického Ústavu ČSAV: Praha, Czech Republic, 1976.

12. Saleem, N.; Abbas, M.; De la Sen, M. Optimal Approximate Solution of Coincidence Point Equations in Fuzzy Metric Spaces. Mathematics 2019, 7, 327.

13. Alolaiyan, H.; Saleem, N.; Abbas, M. A natural selection of a graphic contraction transformation in fuzzy metric spaces. J. Nonlinear Sci. Appl. 2018, 11, 218-227.

14. Butkovic, P. Max-Linear Systems: Theory and Algorithms; Springer: Berlin, Germany, 2010; p. 272.

15. Cuninghame-Green, R.A. Minimax Algebra; Springer: Berlin, Germany, 2012; Volume 166.

16. Gavalec, M. Monotone eigenspace structure in max-min algebra. Linear Algebra Appl. 2002, 345, 149-167.

17. Gavalec, M.; Němcová, Z.; Sergeev, S. Tropical linear algebra with the Łukasiewicz T-norm. Fuzzy Sets Syst. 2015, 276, 131-148.

18. Gavalec, M.; Rashid, I.; Cimler, R. Eigenspace structure of a max-drast fuzzy matrix. Fuzzy Sets Syst. 2014, 249, 100-113.

19. Rashid, I.; Gavalec, M.; Cimler, R. Eigenspace structure of a max-prod fuzzy matrix. Fuzzy Sets Syst. 2016, 303, 136-148.

20. Collins, P.; Niqui, M.; Revol, N. A validated real function calculus. Math. Comput. Sci. 2011, 5, 437-467.

21. Fiedler, M.; Nedoma, J.; Ramík, J.; Rohn, J.; Zimmermann, K. Linear Optimization Problems with Inexact Data; Springer: Berlin, Germany, 2006.

22. Gavalec, M.; Ramík, J.; Zimmermann, K. Interval eigenproblem in max-min algebra. In Decision Making and Optimization; Springer: Berlin, Germany, 2015; pp. 163-181.

23. Litvinov, G.L.; Sobolevskiī, A.N. Idempotent interval analysis and optimization problems. Reliab. Comput. 2001, 7, 353-377.

24. Gavalec, M.; Plavka, J. Monotone interval eigenproblem in max-min algebra. Kybernetika 2010, 46, 387-396.

25. Gavalec, M.; Plavka, J.; Tomášková, H. Interval eigenproblem in max-min algebra. Liner Algebra Appl. 2014, 440, 24-33.

26. Gavalec, M.; Plavka, J.; Ponce, D. Tolerance types of interval eigenvectors in max-plus algebra. Inf. Sci. 2017, 367, 14-27.

27. Gavalec, M.; Zimmermann, K. Classification of solutions to systems of two-sided equations with interval coefficients. Int. J. Pure Appl. Math. 2008, 45, 533.

28. Gavalec, M.; Němcová, Z. Solvability of a Bounded Parametric System in Max-Łukasiewicz Algebra. Mathematics 2020, 8, 1026.

29. Gavalec, M.; Zimmermann, K. Solving systems of two sided (max, min) linear equations. Kybernetika 2010, 46, 405-414.

30. Allamigeon, X.; Fahrenberg, U.; Gaubert, S.; Katz, R.D.; Legay, A. Tropical Fourier-Motzkin elimination, with an application to real-time verification. Int. J. Algebra Comput. 2014, 24, 569-607.