Vivien Delmon. Automata Reduction. CSI Seminar 0830 January 2009

English:

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 au- tomaton 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.

French:

Un automate déterministe peut être minimisé de manière efficace et donne un automate dont le nombre d'états est minimal. L'algorithme de réduction présenté dans ce rapport permet de construire un automate dont le nombre d'états est minimal à partir d'un automate non déterministe dont les poids sont définis sur un semi-anneaux qui est un corps. L'algorithme calcule pour cela la base de l'espace vectoriel engendré par la série représenté par l'au- tomate, ce qui permet de construire un automate dont le nombre d'états est égal à la dimension de cette base. L'algorithme se base sur la représentation matricielle des automates et nous amène à résoudre un système d'équations linéaires, ce qui force le semi-anneau de notre série à avoir les propriétés d'un corps. Nous voulons aussi que notre algorithme fonctionne sur des séries dont le semi-anneaux est un corps non commutatif ce qui nous empêche d'utiliser les techniques classiques de résolution de systèmes linéaires. Ce rapport montre comment passer outre ces difficultés. Nous verrons enfin comment adapter notre algorithme pour qu'il fonctionne sur Z qui n'est pas un corps mais qui possède des propriétés suffisantes.

• Slides : delmon-reduce-slides.pdf
• Report : delmon-reduce-report.pdf

to top