Le genre des langages réguliers
Florian Deloup
IMT, Université Toulouse 2
http://www.math.univ-toulouse.fr/~deloup/
Date(s) : 15/12/2014 iCal
14h00 - 15h00
Il s’agit d’une introduction sur un exemple à l’application de méthodes topologiques à l’étude de la complexité des langages réguliers. Les langages réguliers sont les langages calculés par des automates. En oubliant une partie de sa structure (les étiquettes à valeurs dans un alphabet), un automate est un graphe. On définit le genre d’un langage régulier L comme le genre minimal d’un plongement d’un automate déterministe qui calcule L. Nous montrons que le genre définit une hiérarchie des langages réguliers et qu’il partage certaines propriétés avec la taille. Il est conjecturé que le genre des langages réguliers est calculable. Nous démontrons la conjecture pour certaines classes de langages réguliers sur un alphabet d’au moins trois lettres. Travail en collaboration avec G. Bonfante (Loria, Nancy).
Catégories
