Groupe de Travail

Graphes et Logique


le lundi de 14h à 15h dans l'amphi du LaBRI

Sur le web :
http://www.labri.fr/Perso/~janin/groupe








   


18 Octobre 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.





Responsable du groupe de travail : Olivier Ly
Bureau : 306
Mél: ly@labri.fr
Tél: +33 5 40 00 38 73

Maintenance de la page: Alexis Bouquet
Bureau 325
Mél : bouquet@labri.fr


Archives
This document was tranlated from LATEX by HEVEA and HACHA.