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é:   
La théorie des fonctions de coût régulières
du groupe Graphes et Logique

Date 2012-10-23  11:00-12:00
TitreLa théorie des fonctions de coût régulières 
RésuméLa théorie des fonctions de coûts régulières permet d'étendre quantitativement celle des langages réguliers, et présente plusieurs avantages. Premièrement, les caractérisations en termes d'automates, de monoides ou de logique (MSO,FO,LTL), s'étendent bien dans le cadre des fonctions de coût, et on peut obtenir des généralisations des théorèmes de caractérisation à la Schutzenberger, ainsi que de nouveaux théorèmes propres aux fonctions de coût. Deuxièmement, cette nouvelle théorie permet d'obtenir des résultats difficiles de décidabilité dans la théorie classique des langages réguliers, comme celui du problème de la hauteur d'étoile (qui est à l'origine du développement de cette théorie). On présentera le modèle des fonctions de coût, et on montrera comment les notions classiques sur les langages réguliers (comme celle de monoide syntactique) se généralisent à ce cadre quantitatif. 
Lieusalle 76 
OrateurDenis Kuperberg 
Emaildenis.kuperberg@liafa.univ-paris-diderot.fr  
UrlLiafa 



Aucun document lié à cet événement.

Retour
Retour à l'index