Comparaison approchée des fonctions calculées par automates min-plus

Laure Daviaud
LIF, Aix-Marseille Université
https://www.city.ac.uk/about/people/academics/laure-daviaud

Date(s) : 20/01/2015 iCal
11h05 - 12h00

$Les automates min-plus sont des automates pondérés sur le semi-anneau $(N U \{+\infty\},min,+)$ qui calculent des fonctions de l’ensemble des mots (sur un alphabet fini) dans $N U \{+\infty\}$.
Le problème de tester si $f<g$ pour deux telles fonctions est un problème indécidable (Krob, 92). Néanmoins, nous verrons qu’une approximation de ce problème devient décidable :
il existe un algorithme qui étant donné $e>0$ et deux fonctions f et g calculées par automates min-plus, répond « oui » si $f<g$, « non » s’il existe un mot w tel que $f(w)>(1+e)g(w)$, 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 (LIAFA).$

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