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

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.