Bastien le Gloannec (LIFO, Orléans)

Les tuiles de Wang constituent une manière syntaxique élémentaire et universelle de décrire des ensembles de coloriages du plan discret vérifiant des contraintes locales, c’est-à-dire portant sur les motifs finis autorisés à apparaître ou non. Ces coloriages sont alors appelés pavages. Dans cet exposé, nous nous intéressons aux propriétés des ensembles de pavages engendrés par des jeux de tuiles de Wang exhibant une ou plusieurs directions de déterminisme local, originellement étudiés pour leur proximité avec les automates cellulaires uni-dimensionnels. Après avoir introduit le modèle, nous étudions plusieurs problèmes de décision ou de reconnaissance sur ces objets et présentons plusieurs résultats récents issus de constructions.

Côté décision, nous complétons le résultat d’indécidabilité du problème du pavage dans le cadre 4-way déterministe, établi par Lukkarila en 2009, en montrant l’indécidabilité du problème du pavage périodique 4-way déterministe. Nous présentons également brièvement une (bi-)déterminisation des constructions de jeux de tuiles point-fixe de Durand, Romashchenko et Shen et ses premières applications.

Côté reconnaissance, nous montrons que des familles complexes de coloriages du plan telles que celles engendrées par les substitutions restent reconnaissables dans un cadre 4-way déterministe. Nous considérons enfin des règles locales de déterminisme à rayon élargi afin de permettre la réalisation localement déterministe de systèmes de particules et collisions et revisitons quelques constructions de la littérature à l’aide de ces nouveaux outils.