# Article

Full entry | PDF   (0.4 MB)
Keywords:
(max,min)-linear equations; two-sided system
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.
References:
[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., 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. MR 0782401
[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. DOI 10.1016/j.dam.2005.09.008 | MR 2203194
[4] Cechlárová, K.: Efficient computation of the greatest eigenvector in fuzzy algebra. Tatra Mt. Math. Publications 12 (1997), 73–79. MR 1607194
[5] Cechlárová, K.: Eigenvectors of interval matrices over max-plus algebra. Discrete Applied Mathematics 150 (2005), Nos. 1–3, 2–15. DOI 10.1016/j.dam.2005.02.016 | MR 2161335
[6] Cuninghame-Green, R. A.: Minimax Algebra. (Lecture Notes in Economics and Mathematical Systems 166.) Springer–Verlag, Berlin 1979. MR 0580321 | 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. DOI 10.1016/S0304-3975(02)00228-1 | MR 1957609 | Zbl 1021.65022
[8] Cuninghame-Green, R. A., Zimmermann, K.: Equation with residual functions. Comment. Math. Univ. Carolinae 42 (2001), 729–740. MR 1883381
[9] Sanchez, E.: Resolution of eigen fuzzy sets equations. Fuzzy Sets and Systems 1 (1978), 69–74. DOI 10.1016/0165-0114(78)90033-7 | MR 0494745 | 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. MR 0521129 | Zbl 0399.03040
[11] Vorobjov, N. N.: Extremal algebra of positive matrices (in Russian). Datenverarbeitung und Kybernetik 3 (1967), 39–71. MR 0216854

Partner of