Search

The behavior of discrete-event systems, in which the individual components move from event to event rather than varying continuously through time, is often described by systems of linear equations in max-min algebra, in which classical addition and multiplication are replaced by ⊕ and ⊗, representing maximum and minimum, respectively. Max-min equations have found a broad area of applications in causal models, which emphasize relationships between input and output variables. Many practical situations can be described using max-min systems of linear equations. We shall deal with a two-sided max-min system of linear equations with unknown column vector x of the form A⊗x⊕c=B⊗x⊕d, where A, B are given square matrices, c, d are column vectors and operations ⊕ and ⊗ are extended to matrices and vectors in the same way as in the classical algebra. We give an equivalent condition for its solvability. For a given max-min objective function f, we consider optimization problem of type f⊤⊗x→max or min constraint to A⊗x⊕c=B⊗x⊕d. We solve the equation in the form f(x)=v on the set of solutions of the equation A⊗x⊕c=B⊗x⊕d and extend the problem to the case of an interval function f and an interval value v. We define several types of the reachability of the interval value v by the interval function f and provide equivalent conditions for them. [ABSTRACT FROM AUTHOR]

The behavior of discrete-event systems, in which the individual components move from event to event rather than varying continuously through time, is often described by systems of linear equations in max-min algebra, in which classical addition and multiplication are replaced by $ \oplus $ and $ {\otimes} $, representing maximum and minimum, respectively. Max-min equations have found a broad area of applications in causal models, which emphasize relationships between input and output variables. Many practical situations can be described using max-min systems of linear equations. We shall deal with a two-sided max-min system of linear equations with unknown column vector $ x $ of the form $ A{\otimes} x{\oplus} c = B{\otimes} x{\oplus} d $, where $ A $, $ B $ are given square matrices, $ c $, $ d $ are column vectors and operations $ \oplus $ and $ {\otimes} $ are extended to matrices and vectors in the same way as in the classical algebra. We give an equivalent condition for its solvability. For a given max-min objective function $ f $, we consider optimization problem of type $ f^\top{\otimes} x\rightarrow \max\text{ or } \min $ constraint to $ A{\otimes} x{\oplus} c = B{\otimes} x{\oplus} d $. We solve the equation in the form $ f(x) = v $ on the set of solutions of the equation $ A{\otimes} x{\oplus} c = B{\otimes} x{\oplus} d $ and extend the problem to the case of an interval function $ {{\boldsymbol{f}}} $ and an interval value $ {{\boldsymbol{v}}} $. We define several types of the reachability of the interval value $ {{\boldsymbol{v}}} $ by the interval function $ {{\boldsymbol{f}}} $ and provide equivalent conditions for them.

Max–min algebra is defined as a linearly ordered set with two binary operations. Classical addition and multiplication are replaced by maximum and minimum, respectively. A square matrix is called robust, if all its orbits converge to an eigenvector. In practice, matrix inputs and start vector inputs are rather contained in some intervals than exact values. Considering matrices and vectors with interval coefficients is therefore of great practical importance. In this paper, we study a special type of the robustness called the X -robustness, the case when a starting vector is limited by a lower bound vector x _ and an upper bound vector x ¯ . If we consider some components of the interval starting vector with the existential quantifier and others with the general quantifier, two new types of X -robustness arise, called X E A -robustness and X A E -robustness. Using a similar quantification of interval matrix elements, we obtain AE/EA- X E A -robustness and AE/EA- X A E -robustness. A complete characterization of AE/EA- X A E -robustness and AE/EA- X E A -robustness for a special type of interval matrices, so-called interval circulant matrices, is presented. [ABSTRACT FROM AUTHOR]

In max-min algebra the standard pair of operations plus and times is replaced by the pair of operations maximum and minimum, respectively. A max-min matrix A is called strongly robust if the orbit x;A x;A2 x;: :: reaches the greatest eigenvector with any starting vector. We study a special type of the strong robustness called the strong X-robustness, the case that a starting vector is limited by a lower bound vector and an upper bound vector. The equivalent condition for the strong X-robustness is introduced and efficient algorithms for verifying the strong X-robustness is described. The strong X-robustness of a max-min matrix is extended to interval vectors X and interval matrices A using for-all-exists quantification of their interval and matrix entries. A complete characterization of AE/EA strong X-robustness of interval circulant matrices is presented. [ABSTRACT FROM AUTHOR]

In max-min fuzzy algebra, the study of eigenvectors is important because it can help us to recognize the steady states of systems working in discrete steps. This paper investigates the properties of steady states described by max-min matrices and vectors with interval coefficients. The characteristics of the eigenspace structure and polynomial-time algorithms for recognition of tolerable and weakly-tolerable interval eigenvectors in max-min algebra are described. This research is a continuation of an earlier investigation concerning strongly-tolerable interval eigenvectors. [ABSTRACT FROM AUTHOR]

Max-min algebra is defined as a linearly ordered set with two binary operations. Classical addition and multiplication are replaced by maximum and minimum, respectively. A square matrix is robust, if its eigenspace is achieved starting at arbitrary vector and it is X -robust if its eigenspace is achieved starting at each vector from a given interval vector X . The EA and AE robustness and X -robustness of interval circulant matrices over max-min algebra are defined. Polynomial algorithms for checking these types of robustness and X -robustness are given. [ABSTRACT FROM AUTHOR]

Max-min algebra is an algebraic structure in which classical addition and multiplication are replaced by maximum and minimum, respectively. The notation A ⊗ X ⊗ C = B , where A , B , and C are given interval matrices, represents an interval max-min matrix equation. The paper deals with the solvability of interval matrix equations in max-min algebra. We define three types of solvability of interval max-min matrix equations, namely the strongly universal, universal and weakly universal solvability. We provide the equivalent conditions for each type of solvability that can be verified in polynomial times. [ABSTRACT FROM AUTHOR]

In max-min algebra the standard pair of operations: plus and times is substituted by pair of operations ⊕ and ⊗, where a ⊕ b = max ⁡ { a , b } , a ⊗ b = min ⁡ { a , b }. A square matrix A is X − robust if its eigenspace is reached starting at each vector of a given interval vector X = { x ; x _ ≤ x ≤ x ‾ }. Various versions of the reachability for an interval vector X and an interval matrix A = { A ; A _ ≤ A ≤ A ‾ } depending on the used quantifiers and their order are studied. The universal, possible, tolerance and weak tolerance A -robustness of X and X -robustness of A over max-min algebra are defined and polynomial algorithms for its checking in the case of circulant matrices are described. [ABSTRACT FROM AUTHOR]

In max–min fuzzy algebra, the standard pair of operations—plus and times—is substituted by a different pair of operations—maximum and minimum—which are involved in many optimization problems. Investigation of the properties of eigenvectors is important for these applications. The values of vector or matrix inputs in practice are usually not exact numbers and some intervals can instead be considered as values. This paper investigates the properties of matrices and vectors with interval coefficients. In addition, a complete solution of the strong tolerance interval eigenproblem in max–min algebra is presented. • The eigenproblem in max–min algebra for matrices and vectors with interval coefficients is investigated. • The strong tolerance interval eigenproblem has been completely solved. • Preserving the interval security level in computer net with data storage units and logical units is described. [ABSTRACT FROM AUTHOR]

The max-Łukasiewicz algebra describes fuzzy systems working in discrete time which are based on two binary operations: the maximum and the Łukasiewicz triangular norm. The behavior of such a system in time depends on the solvability of the corresponding bounded parametric max-linear system. The aim of this study is to describe an algorithm recognizing for which values of the parameter the given bounded parametric max-linear system has a solution—represented by an appropriate state of the fuzzy system in consideration. Necessary and sufficient conditions of the solvability have been found and a polynomial recognition algorithm has been described. The correctness of the algorithm has been verified. The presented polynomial algorithm consists of three parts depending on the entries of the transition matrix and the required state vector. The results are illustrated by numerical examples. The presented results can be also applied in the study of the max-Łukasiewicz systems with interval coefficients. Furthermore, Łukasiewicz arithmetical conjunction can be used in various types of models, for example, in cash-flow system.

Ternary reversible logic is a promising choice for low-power implementation and is also physically realizable in quantum computation. Two previous methods for ternary reversible circuit synthesis are based on TGFSOPs and Max-Min algebra. Both require high quantum cost and a large number of ancilla inputs. We propose an alternative Max-Min algebra-based method, where ternary logic functions are represented as Max-Min expressions and are realized using multiple-controlled unary gates. We also propose quantum-level realizations of multiplecontrolled unary gates. We introduce minimization of Max-Min expressions using K-maps and then propose a hybrid genetic algorithm-based method for minimization and synthesis of ternary reversible circuits. We experimented with 24 benchmark functions of up to five variables. On average our method requires 41.36% lower quantum cost and 35.72% fewer ancilla inputs than the method based on TGFSOPs, and 74.39% fewer ancilla inputs than the previously proposed Max-Min algebrabased method. [ABSTRACT FROM AUTHOR]

A matrix A is said to have X-simple image eigenspace if any eigenvector x belonging to the interval X = fx: x ≤ x ≤ xg containing a constant vector is the unique solution of the system A y = x in X. The main result of this paper is an extension of X-simplicity to interval max-min matrix A = fA: A ≤ A ≤ Ag distinguishing two possibilities, that at least one matrix or all matrices from a given interval have X-simple image eigenspace. X-simplicity of interval matrices in max-min algebra are studied and equivalent conditions for interval matrices which have X-simple image eigenspace are presented. The characterized property is related to and motivated by the general development of tropical linear algebra and interval analysis, as well as the notions of simple image set and weak robustness (or weak stability) that have been studied in max-min and max-plus algebras. [ABSTRACT FROM AUTHOR]

An n ×n interval matrix A = [A, A] is called to be a fuzzy interval matrix if 0 ≤ Aij ≤ Aij ≤ 1 for all 1 ≤ i, j ≤ n. In this paper, we proposed the notion of max-min algebra of fuzzy interval matrices. We show that the max-min powers of a fuzzy interval matrix either converge or oscillate with a finite period. Conditions for limiting behavior of powers of a fuzzy interval matrix are established. Some properties of fuzzy interval matrices in max-min algebra are derived. Necessary and sufficient conditions for the powers of a fuzzy interval matrices in max-min algebra to be nilpotent are proposed as well. [ABSTRACT FROM AUTHOR]

A tropical polynomial in nr variables, divided into blocks of r variables each, is r -symmetric if it is invariant under the action of S n that permutes the blocks. For r = 1 we call these symmetric tropical polynomials. We can define r -symmetric and symmetric tropical rational functions in a similar manner. In this paper we identify generators for the sets of symmetric tropical polynomials and rational functions. While r -symmetric tropical polynomials are not finitely generated for r ≥ 2 , we show that r -symmetric tropical rational functions are and provide a list of generators. [ABSTRACT FROM AUTHOR]

We introduce a notion of dimension of max–min convex sets, following the approach of tropical convexity. We introduce a max–min analogue of the tropical rank of a matrix and show that it is equal to the dimension of the associated polytope. We describe the relation between this rank and the notion of strong regularity in max–min algebra, which is traditionally defined in terms of unique solvability of linear systems and the trapezoidal property. [ABSTRACT FROM AUTHOR]

Abstract: Interval eigenvectors of interval matrices in max–min algebra are investigated. The characterization of interval eigenvectors which has been presented in [7] for increasing eigenvectors, is extended here to general interval eigenvectors. Classification types of general interval eigenvectors are studied and characterization of all possible six types is presented. [Copyright &y& Elsevier]

Abstract: In a Coalitional Resource Game (CRG for brief), agents form coalitions to pool their resources in order to achieve certain goals, requiring the expenditure of these resources. A particular coalition is said to be successful, if the common resources of its members enable to achieve a set of goals that satisfies all members of the coalition. It is known that when resources are consumable it is NP-complete to decide whether a given coalition is successful. In this paper, we show a connection of CRGs with sharable resources and max–min linear systems of inequalities. This correspondence leads to polynomial algorithms for checking whether a given CRG admits a successful coalition and for several other problems whose counterparts for CRGs with consumable resources are hard. On the other hand, we prove that some problems concerning the structure of successful coalitions are hard also in the case of sharable resources. [Copyright &y& Elsevier]

In this paper, the minimal solutions of max–min fuzzy relational equations are investigated. A sufficient and necessary condition, for discriminating whether a given solution is minimal or not, is shown. Furthermore, we propose a new algorithm for computing all minimal solutions less than or equal to a given one. [Copyright &y& Elsevier]

Abstract: A speed-up of a known O(n 3) algorithm computing the period of a periodic orbit in max–min algebra is presented. If the critical components (or the transitive closure A +) of the transition matrix A are known, the computational complexity of the algorithm is O(n 2). This is achieved by using only those coordinates of the orbit that are related to the critical components. On the other hand, no critical component can be omitted. As the critical components are pairwise disjoint, the new formula is helpful also in solving the converse problem: generating an orbit with a prescribed period. This is demonstrated by examples. All parts of the paper are connected with the fact that the periodic regime of an orbit is encoded in its critical coordinates. We show that the non-critical coordinates of the state vector after n −1 steps can be ignored, how to generate a known periodic regime by using a small number of coordinates of the state vector and that the difference between the defect of an orbit and the quasidefect of its critical coordinates is small. The final part deals with the situation when the matrix is reduced after the orbit has reached its periodic regime. [Copyright &y& Elsevier]

Abstract: For a given linear mapping, determined by a square matrix in a max–min algebra, the set consisting of all vectors with a unique pre-image (in short: the simple image set of ) is considered. It is shown that if the matrix is generally trapezoidal, then the closure of is a subset of the set of all eigenvectors of . In the general case, there is a permutation , such that the closure of is a subset of the set of all eigenvectors permuted by . The simple image set of the matrix square and the topological aspects of the problem are also described. [Copyright &y& Elsevier]

Abstract: For solving the linear system A ⊗ x = b we introduce some iteration algorithms, where A =(a ij ) and b = b i a given matrix and a column vector with elements from a Brouwerian lattice, and ⊗ is a max–min composite operation. [Copyright &y& Elsevier]

Abstract: Properties of orbits in max–min algebra are described, mainly the properties of periodic orbits. An O(n 3) algorithm computing the period of a periodic orbit is presented. As a consequence, an O(n 3 log n) algorithm computing the period of arbitrary orbit is obtained, as the pre-periodic part of the orbit has length at most (n −1)2 +1. [Copyright &y& Elsevier]

Abstract: For solvable systems of linear equations of the form A ⊗ x = b over the max–min algebra , we propose efficient methods for finding fuzzy determinant and fuzzy solution. We formulate a condition for linear systems of equations over to have not a unique solution by using fuzzy determinant. [Copyright &y& Elsevier]

For unsolvable systems of linear equations of the form A ⊗ χ = b over the max-rain algebra R = ([0, 1], ⊕ = max, × = min), we propose an efficient method for finding a Chebychev-best approximation b̂ ∈ R(m) of the vector b ∈ R(m) in the set S(A) = {b̂ ∈ R(m); A × χ = b̂ is solvable}. Moreover an algorithm for testing the method is reviewed. [ABSTRACT FROM AUTHOR]

The problem of the strong regularity of a square matrix in a general max–min algebra is considered and a necessary and sufficient condition using the trapezoidal property is described. The results are valid without any restrictions on the underlying max–min algebra, concerning the density, or the boundedness. Previous results on this topic are special cases of the theorems presented in this paper. [Copyright &y& Elsevier]

The problem of the strong regularity for square matrices over a general max–min algebra is considered. An O(n2logn) algorithm for recognition of the strong regularity of a given n×n matrix is proposed. The algorithm works without any restrictions on the underlying max–min algebra, concerning the density, or the boundedness. [Copyright &y& Elsevier]

For a given n×n matrix A in a max-min algebra, the set of all increasing eigenvectors, in notation F⩽(A) is studied. It is shown that F⩽(A) is a union of at most 2n−1 intervals, and an explicit formula for the intervals is given. Moreover, it is shown that the endpoints of these intervals can be computed in O(n2) time or in O(n) time, if an auxiliary n×n matrix C(A) has been previously computed. The results enable a complete description of the structure of the whole eigenspace F(A). [Copyright &y& Elsevier]

The max-Łukasiewicz algebra describes fuzzy systems working in discrete time which are based on two binary operations: the maximum and the Łukasiewicz triangular norm. The behavior of such a system in time depends on the solvability of the corresponding bounded parametric max-linear system. The aim of this study is to describe an algorithm recognizing for which values of the parameter the given bounded parametric max-linear system has a solution—represented by an appropriate state of the fuzzy system in consideration. Necessary and sufficient conditions of the solvability have been found and a polynomial recognition algorithm has been described. The correctness of the algorithm has been verified. The presented polynomial algorithm consists of three parts depending on the entries of the transition matrix and the required state vector. The results are illustrated by numerical examples. The presented results can be also applied in the study of the max-Łukasiewicz systems with interval coefficients. Furthermore, Łukasiewicz arithmetical conjunction can be used in various types of models, for example, in cash-flow system. [ABSTRACT FROM AUTHOR]