Des Algorithmes pour tester les  -codes

Xavier AUGROS

(I3S, Nice)

Résumé Soit  un alphabet,  est l'ensemble des mots finis sur  .  est l'ensemble des mots infinis sur  . Un langage L de  est un code si et seulement si chaque mot de  a une unique factorisation sur L. L est un  -code si et seulement si chaque mot de  a une unique factorisation sur L.

Les méthodes connues pour décider si un langage est un  -code nécessitent le calcul de la puissance  du langage. On propose ici deux algorithmes qui n'utilisent pas l'opération puissance-  :
- le premier dans le cas des langages finis, basé sur la construction du graphe des retards. Ce graphe pouvant alors être vu comme un automate reconnaissant les mots (fini ou infini) qui ont plusieurs factorisations sur L.
- le second dans le cas des langages rationnels.

Ces deux algorithmes ont des complexités polynomiales.