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 25 Octobre 2016

Une simulation des voisinages ronds par le voisinage de von Neumann dans les automates cellullaires bidimensionnels

par Anael Grandjean (LIRMM)

Quelle que soit leur dimension, les automates cellulaires sont définis vis-à-vis d'un voisinage, c'est à dire de la manière dont les cellules peuvent communiquer entre elles. Le choix de ce voisinage induit des différences sur les capacités algorithmiques des automates cellulaires. En se restreignant à certains voisinages « raisonnables », on peut montrer que cette différence algorithmique n'a pas d’influence sur les classes de complexité connues (P, NP, PSPACE...). Cette différence, cependant, a un impact fort sur les capacités de reconnaissance en temps réel (le temps de lire l'entrée) des automates cellulaires.

C'est dans le cadre des automates en deux dimensions qu'on va montrer que tous les voisinages d'une certaine forme (les voisinages losanges) permettent de reconnaître les mêmes langages en temps réel que le voisinage de von Neumann. Grâce à cette équivalence, on peut exhiber un ensemble de voisinages (les voisinages ronds) qui permettent de reconnaître strictement moins de langages en temps réel.

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