Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 18 Septembre 2018

Caractérisation logique de la complexité d'un automate cellulaire

par 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.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr