Approche fonctorielle des automates boustrophédons et des automates d’arbres
Victor Iwaniack
I2M, Aix-Marseille
Date(s) : 08/01/2026 iCal
11h00 - 12h30
Dans leur article [1], Colcombet et Petrişan donnent une description des langages et des automates en tant que foncteurs : la reconnaissance devient l’extension d’un langage-en-tant-que-foncteur par un automate-en-tant-que-foncteur. Ils montrent également comment le résultat classique de la minimisation des automates peut être retrouvé dans ce cadre à l’aide d’outils purement catégoriels tels que les extensions Kan et les systèmes orthogonaux de factorisation. Dans cet exposé, je vais donner deux nouveaux types d’automates que nous pouvons voir comme des foncteurs : les automates boustrophédons et les automates d’arbres. Pour le premier type, nous utilisons le point de vue fonctoriel pour déduire catégoriquement une « construction de Shepherdson » transformant un automate boustrophédon en automate classique (donc à sens unique de lecture). Pour le deuxième type, qui prend en entrée des arbres au lieu de mots, nous adaptons le processus de minimisation fonctorielle pour retrouver la minimisation des automates d’arbres.
[1] Thomas Colcombet and Daniela Petrişan. “Automata Minimization: A Functorial Approach”. In: Logical Methods in Computer Science 16.1 (Mar. 2020), Issue 1, 18605974. DOI: 10.23638/LMCS-16(1:32)2020.
Emplacement
I2M Luminy - TPR2, Salle de Séminaire 304-306 (3ème étage)
Catégories
