Automata Reduction

From LRDE

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

Abstract

A deterministic automaton can be minimized efficiently into an automaton that has a minimal number of states. The reduction algorithm presented here produces an automaton with a minimal number of states from a non deterministic automaton with weights defined in a field. This algorithm computes the base of the vector space generated by the series represented by the automaton and produces an automaton with a number of states equal to the dimension of this base. To find this base the algorithm has to solve a system of linear equations, this step requires the semiring to be a field. We also want to run our algorithm on fields that are not commutative which forbids the use of classical solvers for these systems. This report shows how we deal with these different constraints. We also present a modified algorithm to work with series over Z semiring which is not a field but has some sufficient properties.