Une accélération des automates finis multitêtes oublieux par les automates cellulaires

February 3, 2014

Alex Borello (LACL - UPEC)

Les automates cellulaires constituent un modèle de calcul massivement parallèle. On ne sait cependant pas si ce parallélisme lui permet d’être plus rapide, dans le cas général, qu’un modèle séquentiel. En particulier, on ne sait simuler une machine de Turing quelconque qu’avec un automate cellulaire qui, au mieux, effectue son calcul à la même vitesse ; et même avec des modèles séquentiels plus simples, comme les automates finis multitêtes (qui sont des machines de Turing à un ruban en lecture seule et avec plusieurs têtes de lecture), on ne sait pas s’il est toujours possible d’accélérer les calculs avec une simulation par automate cellulaire. Néanmoins, c’est possible si l’on se restreint aux automates finis multitêtes oublieux, c’est-à-dire dont la trajectoire des têtes de lecture sur un mot d’entrée ne dépend que de la taille dudit mot et non des lettres qui le composent. C’est un modèle de reconnaissance de langages simple, mais loin d’être trivial, puisque les langages reconnus constituent la classe NC1. Dans ce travail commun avec Gaétan Richard et Véronique Terrier du GREYC présenté à STACS 2011, on montre qu’un tel automate à k têtes, qui fonctionne en temps O(n^k), peut être simulé par un automate cellulaire fonctionnant en temps O(n^(k – 1)log(n)) et espace O(n^(k – 1)).