Reachability problems for products of matrices in semirings

STÉPHANE GAUBERT; RICARDO D. KATZ

INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION

World Scientific Publishing

Año: 2006 vol. 16 p. 603 - 627

0218-1967

We consider the following matrix reachability problem: given $r$ square matrices with entries in a semiring, is there a product of these matrices which  attains a prescribed matrix? Similarly, we define the vector (resp. scalar) reachability problem, by requiring that the matrix product, acting by right multiplication on a prescribed row vector, gives another prescribed row vector (resp. when multiplied on the left and right by prescribed row and column vectors, gives a prescribed scalar). We show that over any semiring, scalar reachability reduces to vector reachability which is equivalent to matrix reachability, and that for any of these problems, the specialization to any $r >= 2$ is equivalent to the specialization to $r=2$. As an application of these reductions and of a theorem of Krob, we show that when $r=2$, the vector and matrix reachability problems are undecidable over the max-plus semiring $(Z cup{-infty},max,+)$. These reductions also improve known results concerning the classical zero corner problem. Finally, we show that the matrix, vector, and scalar reachability problems are decidable over semirings whose elements are ``positive´´, like the tropical semiring $(N cup{+infty},min,+)$.