Equivalence, reduction and minimization of finite automata over semirings

AbstractA new unified approach to equivalence, reduction and minimization of finite automata over semirings, based on free semimodules, is presented. It includes as special cases deterministic, nondeterministic, stochastic and fuzzy automata. A necessary and sufficient condition for the existence of a finite behaviour matrix for a given automaton is proved. Different algorithmical decidability properties for equivalence, reduction and minimization are connected to a Noetherian property in the category S Modc of the semimodules over the semiring C