Quelques propriétés des automates cellulaires one-way

Alex Borello (LIF) - Jeudi 26 novembre - Frumam.

Les automates cellulaires constituent un modèle de calcul massivement parallèle qui peut être employé, à l'instar des machines de Turing, à la reconnaissance de langages. La classe de complexité (non triviale) la plus faible que l'on peut définir pour ce modèle est nommée “temps réel”. On s'intéresse à la restriction de cette classe de langages aux automates one-way, dans l'optique (encore lointaine) de la caractériser.