Théo Grente (GREYC, Caen)

Les automates cellulaires représentent le modèle par excellence du calcul parallèle et local. De la même façon qu’on sait caractériser en logique 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 prédécesseur.

Dans cet exposé, je présenterai l’exemple du temps réel (= temps minimal) des automates cellulaires, intéressant par sa puissance de reconnaissance (multiplication d’entiers, majorité…) et son polymorphisme.