Résumé :
Plusieurs constructions structurelles pour automates sont basées
sur une expansion qui respecte les calculs réussis et explicite une
proprieté d'interêt. Cette approche peut être formalisée dans la notion
de revêtement d'automates.
Nous présenterons dans un premier temps une manière de construire des
revêtements, que nous appellerons revêtement lexicographique. L'idée est
de classifier les calculs réussis d'un automate (vus comme des mots sur
l'alphabet des transitions) selon un ordre lexicographique. Nous
discuterons des applications de cette méthode pour construire un
N-automate qui reconnaît la différence entre une N-série rationnelle s
et un entier k, et pour construire une décomposition d'une relation
rationnelle k-valuée dans une somme de k fonctions rationnelles. La
taille de notre réponse pour le premier problème est exponentielle,
alors que la réponse connue consiste a itérer k fois une construction de
taille exponentielle pour s - 1.
Ensuite, nous discuterons une preuve pour le problème de décider si
une relation rationnelle est k-valuée. Une réponse positive, en
complexité polynomiale, a été donnée par Gurari et Ibarra en 1983, avec
une réduction au problème de tester le vide pour une classe d'automates
à compteurs. Nous présenterons une preuve qui généralise une
construction dûe à Béal et al. pour tester si un transducteur réalise
une fonction. La complexité de notre preuve semble être meilleure que
celle de Gurari et Ibarra.
Travail en collaboration avec Jacques Sakarovitch.