Characterisation and programming in language theory and in logic of effective complexity classes of cellular automatons

Les automates cellulaires constituent le modèle de calcul parallèle et local par excellence.Comme pour tout modèle du parallélisme, leur programmation est réputée difficile. La puissance de calcul des automates cellulaires, modèle le plus simple du parallélisme, est attestée par le fait que nombre de problèmes significatifs sont calculés en temps minimal, appelé temps-réel, surautomate cellulaire.Principal résultat de cette thèse, on démontre des liens exacts (des équivalences) entre d’un côté la complexité descriptive, essentiellement la définissabilité en logique du second ordre existentiel sur des formules de Horn, de l’autre les classes de complexité en temps-réel des automates cellulaires.Au-delà de cette caractérisation en logique de la complexité en temps minimal, la thèse établit une méthode de programmation parallèle. Cette méthode consiste dans un premier temps à programmer dans nos logiques de Horn l’induction résolvant un problème, puis dans un secondtemps, à appliquer un processus automatique aboutissant au programme de l’automate cellulaire résolvant le problème. Pour justifier l’intérêt de la méthode, la thèse présente un ensemble de programmes logiques pour une variété représentative de problèmes classiques connus pour êtrecalculables en temps-réel sur automates cellulaires.Par ailleurs, toujours en passant par nos logiques, on prouve divers résultats liant le temps-réel des automates cellulaires et les grammaires formelles. Typiquement, tout langage généré par une grammaire algébrique et, plus généralement, une grammaire conjonctive d’Okhotin, est reconnu en temps-réel sur un automate cellulaire de dimension 2.Cellular automata constitute the model of parallel and local computation by excellence.As for any model of parallelism, their programming is known to be difficult. The computingpower of cellular automata, the simplest model of parallelism, is attested by the fact that manysignificant problems are computed in minimal time, called real-time, on cellular automata.The main result of this thesis is the demonstration of exact links (equivalences) between, on onehand, the descriptive complexity, essentially the definability in existential second order logic on Horn formulas, and, on the other hand, the real-time complexity classes of cellular automata.Beyond this characterization in logic of the complexity in minimal time, the thesis establishes a method of parallel programming. This method consists first of all in programming in our Horn ogics the induction solving a problem, then in a second step, in applying an automatic process leading to the program of the cellular automaton solving the problem. To justify the interest of the method, the thesis presents a set of logic programs for a representative variety of classical problems known to be computable in real-time on cellular automata.In addition, we prove various results linking the real time of cellular automata and formal grammars. Typically, any language generated by an algebraic grammar and, more generally, an Okhotin conjunctive grammar, is recognized in real-time on a 2-dimensional cellular automaton