Automates sur mots infinis
Cours de recherche (30h de cours, travail
sur des articles scientifiques)
Cours : Olivier Finkel (Olivier.Finkel)
Les automates sur mots infinis ont été introduits par Büchi dans
les années 1960 pour étudier la décidabilité de la théorie d'un
successeur sur les entiers. Ils ont depuis été très étudiés et
utilisés pour la spécification et la vérification de systèmes ne
terminant pas, comme un système d'exploitation.
La théorie des automates lisant des mots infinis a des liens avec de
nombreux domaines, en particulier avec la topologie, la logique, les
jeux infinis qui modélisent le comportement d'un système en
interaction avec un environnement.
On présentera les notions classiques d'acceptation de mots infinis
par automates finis et on étudiera les aspects fondamentaux de cette
théorie. On abordera l'étude des jeux infinis, modélisant le
comportement d'un système en interaction avec un environnement, et
la construction de stratégies gagnantes effectives dans ces jeux.
Cette construction correspond à la synthèse de programmes dans les
systèmes réactifs.
En fonction du temps, plusieurs extensions seront considérées, comme :
-
Les automates temporisés
- Les automates d'arbres infinis
- Les automates sur mots de longueur transfinie
- Les automates sur mots doubles infinis (figures)
Bibliographie
-
J.R. Büchi, On a Decision Method in Restricted
Second Order Arithmetic, Logic Methodology and Philosophy of Science, (Proc. 1960 Int. Congr.), Stanford
University Press, 1962, p. 1-11.
- E. Gräedel, W. Thomas, and T. Wilke (editors), Automata, Logics, and Infinite Games, A Guide to Current Research,
Lecture Notes in Computer Science, Volume 2500, Springer, 2002.
- D. Perrin and J.-E. Pin, Infinite Words, Automata, Semigroups, Logic and Games, Volume 141 of
Pure and Applied Mathematics, Elsevier, 2004.
- L. Staiger, ω-Languages,
in Handbook of Formal Languages, Volume 3,
edited by G. Rozenberg and A. Salomaa, Springer-Verlag, Berlin, 1997.
- W. Thomas, Automata on Infinite Objects, in: J. Van Leeuwen, ed.,
Handbook of Theoretical Computer Science, Volume B, Elsevier, Amsterdam, 1990, p. 133-191.
- W. Thomas, Languages, Automata and Logic, in Handbook of Formal
Languages, Volume 3, edited by G. Rozenberg and A. Salomaa, Springer Verlag, Berlin, 1997.