Evènement pour le 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. 
OrateurSylvain Lombardy 

Aucun document lié à cet événement.

Retour à l'index