http://www.labri.fr/Perso/~janin/groupe
|
|
![]() |
Sur la théorie monadique des poêles finies |
David Janin | |
Résumé :
(joint work with Anuj Dawar, Cambridge). Les poêles finies sont les codages graphiques des mots infinis ultimement périodiques. On se propose ici d'étudier la logique monadique du second ordre sur les poêles en s'intéressant tout particulièrement aux formules qui ne distingue pas deux poêles codant le même mot (i.e. formule dites invariante par développement finis de poêles). On obtient alors la caractérisation suivante de ces formules de poêles. Thm 1 : pour tout langage omega-rationnel L : la classe des poêles codant les mots ultimement périodiques de L est définissable dans le fragment existentielle de la logique monadique. Thm 2 : pour toute formule de logique monadique phi invariante par développement de poêle, il existe un langage omega-rationnel L dont les mots ultimement périodiques sont exactement les mots codés par les poêles de phi. Autrement dit, on obtiend ici une reformulation du théorème de Büchi applicable aux représentations finis des mots là ou le théorème de Büchi s'applique sur la théorie monadique de l'ordinal omega. Techniquement, ces résultats s'appuient largement sur la théorie classique des langages omega-rationels sans pour autant (semble tiil) en être des conséquences immédiates. |
This document was tranlated from LATEX by HEVEA and HACHA.