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
11 h 05 min - 12 h 00 min

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



Retour en haut