# Comparaison approchée des fonctions calculées par automates min-plus Laure Daviaud
LIF, Aix-Marseille Université

Date(s) : 20/01/2015   iCal
11 h 05 min - 12 h 00 min

$Les automates min-plus sont des automates pondérés sur le semi-anneau \left(N U \\left\{+\infty\\right\},min,+\right) qui calculent des fonctions de l’ensemble des mots \left(sur un alphabet fini\right) dans N U \\left\{+\infty\\right\}. Le problème de tester si f0 et deux fonctions f et g calculées par automates min-plus, répond “oui” si f\left(1+e\right)g\left(w\right), et indifféremment “oui” ou “non” dans les autres cas. La preuve de ce résultat rejoint l’étude des semi-groupes de matrices tropicales finiment engendrés, pour lesquels nous donnons une approximation de l’enveloppe supérieure. Ce travail est un travail commun avec Thomas Colcombet \left(LIAFA\right).$

Approximate comparison of functions calculated by min-plus automata

The min-plus automata are weighted automata on the semiring $(NU \{+\ infty\}, min,+)$ which compute functions of the set of words (on a finite alphabet) in $NU \{+\ infty\}$. The problem of testing whether $f<g$ for two such functions is an undecidable problem (Krob, 92). Nevertheless, we will see that an approximation of this problem becomes decidable: there exists an algorithm which, given $e>0$ and two functions f and g calculated by min-plus automata, answers “yes” if $f<g$, “no” if there exists a word w such as $f (w)>(1+e)g(w)$, and indifferently “yes” or “no” in the other cases. The proof of this result joins l study of finely generated tropical matrix semi-groups, for which we give an approximation of the upper envelope. This work is a joint work with Thomas Colcombet (LIAFA).

https://hal.archives-ouvertes.fr/hal-00712771/

Catégories