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 15 Juin 2010

Bornes inférieures de complexité sur automates cellulaires

par Alex Borello (LIF, Marseille)

Les automates cellulaires constituent un modèle de calcul massivement parallèle qui, à l'instar de celui des machines de Turing, qu'il peut simuler, peut être vu dans le cadre de la reconnaissance de langages. Il est en général difficile d'établir des bornes inférieures sur la puissance de calcul de tels modèles ; ainsi, on connaît peu de techniques permettant d'obtenir des résultats négatifs. On donne ici quelques pistes et exemples en dimension 1 et en temps réel, qui est la plus petite complexité temporelle raisonnable pour ce modèle (au sens où le mot en entrée doit pouvoir être lu entièrement par l'automate considéré).

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