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]

Fuzzy algebra is a special type of algebraic structure in which classical addition and multiplication are replaced by maximum and minimum (denoted ⊗ and ⊗, respectively). The eigenproblem is the search for a vector x (an eigenvector) and a constant λ (an eigenvalue) such that A ⊗ x = λ ⊗ x, where A is a given matrix. This paper investigates a generalization of the eigenproblem in fuzzy algebra. We solve the equation A⊗x = λ⊗B⊗x with given matrices A;B and unknown constant λ and vector x. Generalized eigenvectors have interesting and useful properties in the various computational tasks with inexact (interval) matrix and vector inputs. This paper studies the properties of generalized interval eigenvectors of interval matrices. Three types of generalized interval eigenvectors: strongly tolerable generalized eigenvectors, tolerable generalized eigenvectors and weakly tolerable generalized eigenvectors are proposed and polynomial procedures for testing the obtained equivalent conditions are 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]

Max-plus algebra is the similarity of the classical linear algebra with two binary operations, maximum and addition. The notation Ax = Bx, where A, B are given (interval) matrices, represents (interval) two-sided (max, plus)-linear system. For the solvability of Ax = Bx, there are some pseudopolynomial algorithms, but a polynomial algorithm is still waiting for an appearance. The paper deals with the analysis of solvability of two-sided (max, plus)-linear equations with inexact (interval) data. The purpose of the paper is to get efficient necessary and sufficient conditions for solvability of the interval systems using the property of the solution set of the non-interval system Ax = Bx. The main contribution of the paper is a transformation of weak versions of solvability to either subeigenvector problems or to non-interval two-sided (max, plus)-linear systems and obtaining the equivalent polynomially checked conditions for the strong versions of solvability. [ABSTRACT FROM AUTHOR]