Automates cellulaires (temps réel et voisinages)

Dans cette thèse nous nous sommes intéressés à l'importance du choix du voisinage sur les capacités algorithmiques des automates cellulaires. Nous avons travaillé en dimension quelconque en nous concentrant 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. En effet il est connu que les voisinages sont équivalents en temps linéaire et il est donc nécessaire de considérer des temps inférieurs. Nous avons obtenu plusieurs résultats d'équivalences de voisinages au sens du temps réel (des classes de voisinages tels que les automates fonctionnant sur ces voisinages reconnaissent les mêmes langages) et des résultats d'accélérations linéaires ou constantes selon les voisinages.In this thesis we have worked on the impact of the choice of a neighborhood on the algorithmic abilities of cellular automata. We have specifically studied the lower complexity classes such as the real time (that corresponds to the shortest time necessary for a cellular automaton to read all the letters of the input word) and the real time plus a constant. It is indeed known that neighborhoods are equivalent in linear time and it is therefore necessary to consider shorter times. We have obtained neighborhood equivalence results with respect to the real time (neighborhood classes such that cellular automata working on any of those neighborhoods can recognize the same languages in real time) and linear or constant speed-up theorems for many classes of neighborhoods.LYON-ENS Sciences (693872304) / SudocSudocFranceF