Previous |  Up |  Next


max-min algebra; two-sided linear systems; lower bound; upper bound
Max-min algebra and its various aspects have been intensively studied by many authors [1, 4] because of its applicability to various areas, such as fuzzy system, knowledge management and others. Binary operations of addition and multiplication of real numbers used in classical linear algebra are replaced in max-min algebra by operations of maximum and minimum. We consider two-sided systems of max-min linear equations $A \otimes x = B \otimes x$, with given coefficient matrices $A$ and $B$. We present a polynomial method for finding maximal solutions to such systems, and also when only solutions with prescribed lower and upper bounds are sought.
[1] Baccelli, F. L., Cohen, G., Olsder, G. J., Quadrat, J. P.: Synchronization and Linearity. An Algebra for Discrete Event Systems. Wiley, Chichester 1992. MR 1204266 | Zbl 0824.93003
[2] Butkovič, P., Zimmermann, K.: A strongly polynomial algorithm for solving two-sided systems of (max,plus)-linear equations. Discrete Applied Math. 154 (2006), 437–446. DOI 10.1016/j.dam.2005.09.008 | MR 2203194
[3] Cechlárová, K., Cuninghame-Green, R. A.: Interval systems of max-separable linear equations. Linear Algebra Appl. 340 (2002), 215–224. MR 1869429
[4] Cunninghame-Green, R. A.: Minimax Algebra. (Lecture Notes in Economy and Mathematical Systems 166.) Springer-Verlag, Berlin 1979. MR 0580321
[5] Gavalec, M., Zimmermann, K.: Solving systems of two-sided (max,min)-linear equations. Kybernetika 46 (2010), 405–414. MR 2676078 | Zbl 1195.65037
[6] Sanchez, E.: Resolution of eigen fuzzy sets equations. Fuzzy Sets and System 1 (1978), 69–74. DOI 10.1016/0165-0114(78)90033-7 | MR 0494745 | Zbl 0366.04001
Partner of
EuDML logo