Automates cellulaires: temps réel et voisinages

Les automates cellulaires sont un modèle de calcul élémentaire pemettant d'étudier l'influence du parallélisme sur la complexité du calcul. Dans cet ouvrage, l'auteur étudie l'importance du choix du voisinage sur les capacités algorithmiques des automates cellulaires. L'étude porte principalement sur les classes de complexité correspondant au temps réel (plus petit temps nécessaire pour que l'automate ait lu le mot en entrée) et temps réel plus une constante. Plusieurs résultats d'équivalences de voisinages au sens du temps réel sont obtenus ainsi que des résultats d'accélérations linéaires ou constantes selon les voisinages.