Contribution aux problèmes de réalisation des langages et séries rationnels

Sylvain Lombardy (1)

1 LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications

Une première partie de l'exposé sera consacrée aux automates max-plus et min-plus. Ces automates apparaissent naturellement dans des problèmes d'ordonnancement et dans certains problèmes de la théorie des langages comme la puissance finie ou la hauteur d'étoile. Je montrerai comment décider si un automate max-plus d'ambiguïté bornée réalise une série intrinsèquement non ambiguë, ce qui permet d'étendre la classe de famille dans laquelle la séquentialité des séries rationnelles max-plus est décidable. Par ailleurs, je présenterai le résultat selon lequel toute série qui est à la fois une série rationnelle max-plus et min-plus est en fait une série non ambiguë. La seconde partie de l'exposé portera sur la notion de conjugaison d'automates avec multiplicités, inspirée par la celle de conjugaison des systèmes dynamiques. Nous verrons dans quelle mesure des automates qui réalisent des séries identiques peuvent être reliés par une chaîne de conjugaison. D'autre part, nous donnerons une interprétation de cette définition matricielle en termes de revêtements d'automates. Nous verrons enfin les conséquences de la combinaison de ces deux approches.

Mots clés: langage rationnel; série rationnelle; automate

Domaines: Informatique [cs]

Sylvain Lombardy. Contribution aux problèmes de réalisation des langages et séries rationnels. Informatique [cs]. Université Paris-Diderot - Paris VII, 2005. ⟨tel-00637128⟩