SUPPORTS DE COURS

Cours n°4

Indécidabilité de l'injectivité et de la surjectivité en dimension 2, en s'appuyant sur l'indécidabilité du pavage du plan par des tuiles de Wang. Je me suis appuyé pour ce cours sur les transparents de Nicolas Ollinger : 104 tiles et Pavages : de l'apériodicité à l'indécidabilité

Cours n°6 [pdf]

Reconnaissance de langages sur automates cellulaires. Quelques techniques élémentaires, théorèmes d'accélération constante et linéaire, théorème d'Ibarra.