On max-plus two-sided linear systems whose solution sets are min-plus linear

The max-plus algebra R∪ \-∞ \ is defined in terms of a combination of the following two operations: addition, a ⊕ b := max(a,b), and multiplication, a ⊗ b := a + b. In this study, we propose a new method to characterize the set of all solutions of a max-plus two-sided linear system A ⊗ x = B ⊗ x. We demonstrate that the minimum ``min-plus'' linear subspace containing the ``max-plus'' solution space can be computed by applying the alternating method algorithm, which is a well-known method to compute single solutions of two-sided systems. Further, we derive a sufficient condition for the ``min-plus'' and ``max-plus'' subspaces to be identical. The computational complexity of the method presented in this study is pseudo-polynomial.