Reachability problems for products of matrices in semirings

Stephane Gaubert, Ricardo Katz

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?…