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