zbMATH — the first resource for mathematics

Interval systems of max-separable linear equations. (English) Zbl 1004.15009
The authors formulate some problems for systems of linear equations over max-plus and max-min algebras whenever intervals are known for the given entries. The solutions of these problems are studied and the complexity of the problems is discussed and compared with the complexity of the corresponding problems over the field of real numbers.

15A06 Linear equations (linear algebraic aspects)
15A80 Max-plus and related algebras
65G30 Interval and finite arithmetic
Full Text: DOI
[1] Baccelli, F.L.; Cohen, G.; Olsder, G.J.; Quadrat, J.P., Synchronization and linearity, an algebra for discrete event systems, (1992), Wiley Chichester
[2] Cechlárová, K., A note on unsolvable systems of MAX-MIN (fuzzy) equations, Linear algebra appl., 310, 123-128, (2000) · Zbl 0971.15002
[3] Cechlárová, K.; Diko, P., Resolving infeasibility in extremal algebras, Linear algebra appl., 290, 267-273, (1999) · Zbl 0932.15009
[4] R.A. Cuninghame-Green, Minimax algebra, Lecture Notes in Economics and Mathematical Systems, vol. 166, Springer, Berlin, 1979
[5] Cuninghame-Green, R.A.; Cechlárová, K., Residuation in fuzzy algebra and some applications, Fuzzy sets and systems, 71, 227-239, (1995) · Zbl 0845.04007
[6] K. Cechlárová, R.A. Cuninghame-Green, Solvable approximation of linear systems in max-plus algebra, Proc. 1st Symposium on System Structure and Control, Prague, 2001, to appear
[7] Di Nola, A.; Sessa, S.; Pedrycz, W.; Sanchez, E., Fuzzy relational equations and their applications to knowledge engineering, (1989), Kluwer Dordrecht
[8] Kreinovich, J.; Lakeyev, A.; Rohn, J.; Kahl, P., Computational complexity and feasibility of data processing and interval computations, (1998), Kluwer Dordrecht · Zbl 0945.68077
[9] Lakeyev, A.; Kreinovich, J., NP-hard classes of linear algebraic systems with uncertaintes, Reliable computing, 3, 51-81, (1997) · Zbl 0884.65032
[10] Oettli, W.; Prager, W., Compatibility of approximate solution of linear equations with given error bounds for coefficients and right-hand sides, Numer. math., 6, 405-409, (1964) · Zbl 0133.08603
[11] Rohn, J., Strong solvability of interval linear programming problems, Computing, 26, 79-82, (1981) · Zbl 0449.90062
[12] Rohn, J., Linear programming with inexact data is NP-hard, Zeitschrift für angewandte math. und mechanik, 78, Supplement 3, S1051-S1052, (1998) · Zbl 0915.90204
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.