BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//wp-events-plugin.com//7.2.3.1//EN
TZID:Europe/Paris
X-WR-TIMEZONE:Europe/Paris
BEGIN:VEVENT
UID:8188@i2m.univ-amu.fr
DTSTART;TZID=Europe/Paris:20150120T110500
DTEND;TZID=Europe/Paris:20150120T120000
DTSTAMP:20241120T210100Z
URL:https://www.i2m.univ-amu.fr/evenements/comparaison-approchee-des-fonct
 ions-calculees-par-automates-min-plus/
SUMMARY:Laure Daviaud (LIF\, Aix-Marseille Université): Comparaison approc
 hée des fonctions calculées par automates min-plus
DESCRIPTION:Laure Daviaud:  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 \\{+\\i
 nfty\\}$.\nLe problème de tester si $f&lt\;g$ pour deux telles fonctions 
 est un problème indécidable (Krob\, 92). Néanmoins\, nous verrons qu'un
 e approximation de ce problème devient décidable :\nil existe un algorit
 hme qui étant donné $e&gt\;0$ et deux fonctions f et g calculées par au
 tomates min-plus\, répond "oui" si $f&lt\;g$\, "non" s'il existe un mot w
  tel que $f(w)&gt\;(1+e)g(w)$\, et indifféremment "oui" ou "non" dans les
  autres cas.\nLa preuve de ce résultat rejoint l'étude des semi-groupes 
 de matrices tropicales finiment engendrés\, pour lesquels nous donnons un
 e approximation de l'enveloppe supérieure.\nCe travail est un travail com
 mun avec Thomas Colcombet (LIAFA).\nApproximate comparison of functions ca
 lculated by min-plus automata\nThe 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 pr
 oblem of testing whether $f&lt\;g$ for two such functions is an undecidabl
 e problem (Krob\, 92). Nevertheless\, we will see that an approximation of
  this problem becomes decidable: there exists an algorithm which\, given $
 e&gt\;0$ and two functions f and g calculated by min-plus automata\, answe
 rs "yes" if $f&lt\;g$\, "no" if there exists a word w such as $f (w)&gt\;(
 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-grou
 ps\, for which we give an approximation of the upper envelope. This work i
 s a joint work with Thomas Colcombet (LIAFA).\nhttps://hal.archives-ouvert
 es.fr/hal-00712771/\n\n&nbsp\;
ATTACH;FMTTYPE=image/jpeg:https://www.i2m.univ-amu.fr/wp-content/uploads/2
 020/01/Laure_Daviaud.jpg
CATEGORIES:Séminaire,Ernest
END:VEVENT
BEGIN:VTIMEZONE
TZID:Europe/Paris
X-LIC-LOCATION:Europe/Paris
BEGIN:STANDARD
DTSTART:20141026T020000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
END:STANDARD
END:VTIMEZONE
END:VCALENDAR