Weakly linear systems for matrices over the max-plus quantale

In this paper we introduce and study weakly linear systems, i.e. systems consisting of matrix inequalities Eqs. 17–20, over the max-plus quantale which is also known as complete max-plus algebra. We prove the existence of the greatest solution contained in a given matrix X0, and present a procedure for its computation. In the case of weakly linear systems consisting of finitely many matrix inequalities, when all finite elements of matrices X0, As and Bs, s ∈ I are integers, rationals or particular irrationals and a finite solution exists, the procedure finishes in a finite number of steps. If in that case an arbitrary finite solution is given, a lower bound on the number of computational steps is calculated. Otherwise, we use our algorithm to compute approximations to finite solutions.