Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

Intitulé:   
A separation result on min-plus and max-plus automata
du groupe Séminaire Méthodes Formelles

Date 2020-01-28  07:00-07:00
TitreA separation result on min-plus and max-plus automata 
RésuméWork in collaboration with Thomas Colcombet. The talk shall start with an overview of min-plus and max-plus automata. These weighted automata realize functions which map words onto real numbers. We shall see that it may be thorny to give a description of their asymptotic behaviour. In contrast, it is pretty easy to study the functions realized by unambiguous weighted automata (with at most one accepting run for each input). It was known that a function that can be both realized by a min-plus and a max-plus automaton can actually be realized by an unambiguous one. We show a generalization of this result: if a function realized by a min-plus automaton is larger than a function realized by a max-plus automaton, then there exists an effectively computable unambiguous automaton which realizes a function in between. This result also applies on weighted tree automata. 
Lieu178 
OrateurSylvain Lombardy 
Emailhttps://www.labri.fr/perso/slombard/ 
UrlLaBRI 



Aucun document lié à cet événement.

Retour
Retour à l'index