| Résumé | Dans cet exposé, nous proposerons une extension quantitative
de l'équivalence classique en théorie des langages:
"accepté par automate = reconnaissable par monoïde = définissable en logique MSO".
Les automates considérés étendent les "nested distance desert automata"
de Kirsten, ainsi que les B et les S-automates (présentés à LICS06).
Les monoïdes de stabilisation abstraient des notions classiques
dans l'étude des automates (max,+).
Enfin, on étend la logique MSO de sorte
qu'il devient possible d'exprimer, par exemple, le diamètre d'un graphe.
Des résultats de décisions adaptées seront également fournis. |