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

Carte non disponible

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

Catégories


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 $fil 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(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).

[http://pageperso.lif.univ-mrs.fr/~laure.daviaud/]

Olivier CHABROL
Posts created 14

Articles similaires

Commencez à saisir votre recherche ci-dessus et pressez Entrée pour rechercher. ESC pour annuler.

Retour en haut
Secured By miniOrange