Le genre des langages réguliers

Carte non disponible

Date/heure
Date(s) - 15/12/2014
14 h 00 min - 15 h 00 min

Catégories Pas de Catégories


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).

[http://www.math.univ-toulouse.fr/~deloup/]

Olivier CHABROL
Posts created 14

Articles similaires

Commencez à saisir votre recherche ci-dessus et pressez Entrée pour rechercher. ESC pour annuler.

Retour en haut
Secured By miniOrange