Certain linear and weakly linear systems of matrix equations over semirings. Applications in a state reduction of weighted automata.

Abstract

In this paper we study particular linear and weakly linear systems of matrix equations over semirings, with the aim of describing and computing functions as solutions to those systems. Our special attention is devoted to solutions whose ranks are as small as possible. We prove the existence of solutions with the smallest ranks, give their characterizations, and present a method for their computations. Regarding weakly linear systems, themethod is based on thewell known partition refinement algorithmby Kanellakis and Smolka, adapted toworkwithweighted labeled transition systems. Moreover,we give a state reduction procedure of weighted automata based on a decomposition of solutions to particular linear and weakly
linear systems.