Les automates cellulaires représentent le modèle par excellence du calcul parallèle et local. De la même façon que pour les langages rationnels, on cherche à caractériser/programmer en logique les calculs des automates cellulaires. Le comportement local et déterministe des automates cellulaires s'exprime naturellement par des clauses de Horn portant sur une arithmétique locale du successeur.

Dans cet exposé, on évoquera la caractérisation de deux classes de complexité significatives des automates cellulaires : le temps réel/minimal et le temps linéaire.