Julien Ferté (LIF) - Jeudi 21 Janvier à 17h30 - Frumam.

Je motive l'étude de tels automates par une généralisation de travaux précédents (notamment ceux dus à Sénizergues). Après un bref historique des automates à pile itérée, je mentionnerai quelques thèmes de recherches relatifs à ces automates, et dépeindrai l'état de l'art dans le domaine plus précis des fortement déterministes. Appelons 2-calculables, les fonctions réalisées par les automates à pile de piles. Le but de cet exposé est de montrer dans les grandes lignes l'équivalence en expressivité des fonctions 2-calculables et des fonctions réalisées par les HDT0Ls (définis par Lindenmayer). Ce théorème est assez algébrique, et sert notamment de base à Sénizergues pour montrer un théorème de décomposition des fonctions n-calculables en fonctions 2-calculables. Pour se faire, un autre objet sera défini (les suites récurrentes caténatives), qui servira d'intermédiaire dans la démonstration. Deux ouvertures seront finalement mentionnées, la complexité des passages et des constructions, et l'application possible des outils développés pour la démonstration du théorème à d'autres problèmes.