Modèles de calcul, systèmes dynamiques (voir le chapitre 1 du cours de l'EJCIM 2017 pour plus de précisions sur la partie automates cellulaires/pavage)
-
Automates cellulaires : équivalence des définitions locale et topologique, réversibilité, théorème du jardin d'Éden et de l'équilibre, décidabilité de ces propriétés en 1D et indécidabilité en 2D.
-
Pavages par tuiles de Wang et sous-shifts (de type fini) : indécidabilité du problème du domino, apériodicité, pavages non calculables.
-
Réseaux d'automates booléens : dynamique et structure, expressivité, théorème des points fixes, influence des modes de mise à jour (déterministes et non déterministes), cycles d'interactions, complexité algorithmique.
