Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 24 Février 2015

Tuiles de Wang déterministes : (in)décidabilité et reconnaissance

par 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.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr