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 12 Mars 2013

Ensembles limite d'automates cellulaires

par Alexis Ballier (CMM, Chile)

Les automates cellulaires (AC) servent souvent de modèles de systèmes dynamiques discrets ou comme modèles de calcul et constituent un système complexe: Une définition locale simple mais un comportement global difficile à prédire.

Nous nous intéresserons ainsi à leur comportement à long terme: Les états du système atteignables arbitrairement tard lors de leur évolution, c'est à dire l'ensemble limite de l'automate cellulaire. Si un AC atteint son ensemble limite au bout d'un temps fini il est dit "stable", dans le cas contraire il est dit "instable". Nous montrerons brièvement comment, en collaboration avec Pierre Guillon et Jarkko Kari, nous avons obtenu le premier exemple d'ensemble limite atteignable à la fois par un AC stable et un (autre) AC instable. Ce résultat a donné lieu à une conjecture sur une possible caractérisation des ensembles limite d'ACs stables. Par la suite nous montrerons que les ensembles limite ayant la propriété conjecturée nécessaire correspondent aux ensembles limite d'un certain type d'automates cellulaires stables. Le problème de savoir si tous les ensembles limite d'AC stables peuvent être atteints par ces ACs stables particuliers reste cependant ouvert.

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