Responsable: V. Berthé, Directrice de recherches au CNRS

Ce cours présente des notions classiques relevant de la combinatoire des mots et de l'étude des systèmes dynamiques symboliques.

Intervenants :

- Valérie Berthé, Directrice de recherches au CNRS (12h)

- Olivier Carton, Professeur à l'Université Paris Cité (12h)

Le cours a lieu pendant la seconde période en salle 1002 le mardi de 8h45 à 11h45.

Les dates concernées sont : 10,12,17 décembre, 7,14, janvier, puis 28 janvier, 4,18,25 février. L'unique examen aura lieu le 4 mars.

• 2-8-2 Vérification algorithmique des programmes
• 2-10 Aspects algorithmiques de la combinatoire
• 2-15 Analyse d'algorithmes
• 2-16 Modélisation par automates finis
• 2-17-1 Fondements sur la modélisation des réseaux

Français ou Anglais suivant l'avis des étudiants. L'anglais sera choisi si au moins un étudiant ne connait pas le français.

Le sujet d'examen sera en français et en anglais.

Les étudiants seront autorisés à rédiger leur examen en français ou en anglais.

L’objet de ce cours est de présenter une introduction à la dynamique symbolique. Un système dynamique discret (c’est-à-dire à temps discret) est défini comme l’action d’une application T agissant sur un espace X. Il s'agit alors d’étudier l’évolution à long terme du système. La dynamique symbolique a pour objet l’étude de systèmes dynamiques discrets composés de suites infinies de symboles d’un alphabet fini. Ils apparaissent naturellement comme des codages de trajectoires de points d’un système dynamique défini sur un espace X, a priori de nature continue, selon une partition finie donnée.

Voici quelques thèmes abordés dans ce cours:

• Système dynamique (à temps discret)
• Système sofique, système de type fini
• Entropie
• Complexité en facteurs, mots sturmiens, substitutions
• Mesure de Parry
• Normalité vs compressibilité par automates
• Théorème ergodique

• Cours n° 0 : introduction
• Cours n° 1 : shifts et sous-shifts ([3] p.1, [2] p.34)
  • espaces de suites, distance, topologie
  • équivalence avec l'ensemble des facteurs
  • entropie (existence)
  • exemples
• Cours n° 2 : sous-shifts de type fini et sous-shifts sofiques
  • définitions
  • automates locaux et décidabilité de la localité
• Cours n° 3 : décidabilité du type fini
  • local implique de type fini
  • déterminisation et minimisation d'automates
• Cours n° 4 : applications locales
  • Théorème de Perron-Frobenius (wikipedia, [7], [3, chap 7.1])
  • définition
  • conjugaison de systèmes
  • invariants: entropie et fonction zêta
  • rationalité de la fonction zêta
• Cours n° 5 : substitutions
  • mots et décalages engendrés
  • exemples : Fibonacci, Thue-Morse
  • complexité en facteurs
• Cours n° 6 : substitutions primitives
  • Complexité linéaire
  • Récurrence linéaire
  • Minimalité et uniforme récurrence
• Cours n° 7 : fréquences et équilibre
  • Notion de fréquences uniformes
  • Discrépance symbolique et équilibre
  • Liens avec les fréquences
  • Autour du théorème ergodique (mesures invariantes,unique ergodicité)
• Cours n° 8 : mots sturmiens
  • Graphe des mots
  • Equilibre

Théorie classique des automates finis.

Some notes here

L'évaluation est basée sur deux examens, l'un en milieu de la seconde période et l'autre à la fin de la deuxième période, pendant le créneau habituel du cours. La note finale est la moyenne des notes des deux examens.

Les notes de cours sont autorisées pendant l'examen.

1. M.-P. Béal, D. Perrin, Symbolic dynamics and finite automata, Handbook of formal languages, Vol. 2, 463–505, Springer, Berlin, 1997.
2. M.-P. Béal, Codage symbolique, Masson, 1993.
3. B. P. Kitchens, Symbolic Dynamics: One-sided, two-sided and countable state Markov shifts, Universitext, Springer-Verlag.
4. D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge University Press.
5. N. Pytheas Fogg, Substitutions in Dynamics, Arithmetics and Combinatorics, V. Berthé and S. Ferenczi and C. Mauduit and A. Siegel (eds), Lecture Notes in Mathematics, vol. 1794, Springer-Verlag,
6. Combinatorics, Automata and Number Theory, V. Berthé, M. Rigo (eds.). 2010, Encyclopedia Math. Appl., vol. 135, Cambridge University Press.
7. E. Senata, Non-negative matrices and Markov Chains, Springer Series in Statistics

Les membres des équipes “Combinatoires” et “Automates et applications” de l'IRIF