http://www.lirmm.fr/~poupet/
e-mail: victor.poupet [at] lirmm.fr

Enseignement : Théorie des langages et pavages (1er semestre 2016-2017)

Transparents de cours et fiches de TD utilisées pour le cours de M2 recherche à l'université Montpellier 2.

Floating Isle - -kol
image : Floating Isle - -kol

Supports de cours

Présentation [pdf]

Une présentation générale du module, suivie d'une introduction aux automates cellulaires (définitions et propriétés élémentaires).

Compacité [pdf]

Topologie sur l'espace des configurations et compacité.

Automates cellulaires: Décidabilité en 1D [pdf]

Preuve de la décidabilité de l'injectivité et la surjectivité des automates cellulaires en dimension 1. Preuve de K. Sutner utilisant les graphe de de Bruijn.

Tuiles et pavages [pdf]

Définition des pavages par les tuiles de Wang et par motifs interdits. Présentation du Domino Problem et construction d'un pavage apériodique.

Indécidabilité sur les automates cellulaires [pdf]

Preuve de l'indécidabilité de la surjectivité et de l'injectivité des automates cellulaires 2D. Définition de la notion d'ensemble limite, et indécidabilité de la nilpotence.

Exercices

TD - Théorème de Moore-Myhill [pdf]

Démonstration du théorème de Moore-Myhill (également connu sous le nom de théorème du jardin d'Eden), indiquant qu'un automate cellulaire est surjectif si et seulement il est injectif sur les configurations finies. La preuve repose sur un argument combinatoire.

DM - Automates conservateurs [pdf]

Définition des automates cellulaires conservateurs, propriétés élémentaires et caractérisation de Boccara et Fukś.

Valid XHTML 1.0 Transitional Valid CSS! Valid Konami!