Solving systems of two-sided (max, min)-linear equations. (English) Zbl 1195.65037

Summary: A finite iteration method for solving systems of (max, min)-linear equations is presented. The systems have variables on both sides of the equations. The algorithm has polynomial complexity and may be extended to wider classes of equations with a similar structure.


65F10 Iterative numerical methods for linear systems
08A72 Fuzzy algebraic structures
65Y20 Complexity and performance of numerical algorithms
15A80 Max-plus and related algebras
15B15 Fuzzy matrices
Full Text: EuDML Link


[1] Baccelli, F. L., Cohen, G., Olsder, G. J., Quadrat, J. P.: Synchronization and Linearity. An Algebra for Discrete Event Systems. Wiley, Chichester, 1992. · Zbl 0824.93003
[2] Butkovič, P., Hegedüs, G.: An elimination method for finding all solutions of the system of linear equations over an extremal algebra. Ekonomicko-matematický obzor 20 (1984), 203-215. · Zbl 0545.90101
[3] Butkovič, P., Zimmermann, K.: A strongly polynomial algorithm for solving two-sided linear systems in max-algebra. Discrete Applied Mathematics 154 (2006), 437-446. · Zbl 1090.68119
[4] Cechlárová, K.: Efficient computation of the greatest eigenvector in fuzzy algebra. Tatra Mt. Math. Publications 12 (1997), 73-79. · Zbl 0963.65041
[5] Cechlárová, K.: Eigenvectors of interval matrices over max-plus algebra. Discrete Applied Mathematics 150 (2005), Nos. 1-3, 2-15. · Zbl 1086.15009
[6] Cuninghame-Green, R. A.: Minimax Algebra. (Lecture Notes in Economics and Mathematical Systems 166.) Springer-Verlag, Berlin 1979. · Zbl 0739.90073
[7] Cuninghame-Green, R. A., Butkovič, P.: The equation \(A \otimes x = B \otimes y\) over (max,+). Theoretical Computer Science 293 (2003), 3-12. · Zbl 1021.65022
[8] Cuninghame-Green, R. A., Zimmermann, K.: Equation with residual functions. Comment. Math. Univ. Carolinae 42 (2001), 729-740. · Zbl 1068.93039
[9] Sanchez, E.: Resolution of eigen fuzzy sets equations. Fuzzy Sets and Systems 1 (1978), 69-74. · Zbl 0366.04001
[10] Sanchez, E.: Inverses of fuzzy relations. Applications to possibility distributions and medical diagnosis. Fuzzy Sets and Systems 1 (1978), 75-86. · Zbl 0399.03040
[11] Vorobjov, N. N.: Extremal algebra of positive matrices (in Russian). Datenverarbeitung und Kybernetik 3 (1967), 39-71.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.