Automata Reduction

From LRDE

Revision as of 17:04, 9 January 2018 by Bot (talk | contribs) (Created page with "{{CSIReport | authors = Vivien Delmon | title = Automata Reduction | year = 2008 | abstract = A deterministic automaton can be minimized efficiently into an automaton that has...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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.