Automates à multiplicité dans
et le problème de la hauteur d'étoile :
une introduction

Résumé

Jacques Sakarovitch
E. N. S. T., C. N. R. S., Paris

Nous commencerons par présenter le problème dit ``de la hauteur d'étoile'' des langages rationnels dont l'ancienne dénomination ``loop complexity of automata'' dit clairement l'inspiration machinistique à l'origine: parmi tous les automates équivalents à un automate (fini) donné, sait-on construire, effectivement, un automate dans lequel le nombre de ``boucles imbriquées'' est minimum?

Ce problème, posé en 1963 par Eggan, s'est révélé très difficile et n'a été résolu qu'en 1989 par Hashiguchi. Et encore, sa preuve, dernière étape d'une série d'articles étalée sur dix ans, reste-t-elle obscure et n'a fait l'objet d'aucune présentation didactique (cf. Perrin, art. cit. ).

Au centre de tous les travaux sur cette question, on trouve les automates avec multiplicité dans et les problèmes de décision qui leur sont naturellement associés.

Nous allons l'illustrer avec le problème que j'appellerai de la ``richesse'' d'un langage (si cette expression plaît à mes collègues) et qu'on peut voir comme un cas particulier, particulièrement simple, du problème de la hauteur d'étoile. Je dirai qu'un langage est ``riche'' s'il contient tellement de mots qu'on ne gagne rien à en faire l'étoile par rapport aux simples opérations de produit et d'union. Plus précisément, L est ``riche'' s'il existe un entier k tel que

En 1966, Brzozowski le problème suivant: est-il décidable si un langage rationnel donné est riche ou non? Simon a répondu par l'affirmative en 1978 (Hashiguchi aussi, indépendamment) en montrant
a) que ce problème se ramène à celui de savoir si un monoïde finiment engendré de matrices à coefficients dans est fini,
b) que ce dernier problème est décidable.

C'est évidemment cette deuxième partie qui est la plus substantielle et nous essayerons de la démontrer complètement. Elle doir également être vue comme une introduction au théorème d'Hashiguchi sur les automates avec multiplicité dans (``limitedness theorem''), dont Simon et Leung ont donné des preuves croisées et éclairantes, et qui pourra faire l'objet d'un exposé ultérieur.

Référence:

D. Perrin, Finite Automata, in Handbook of Theoretical Computer Science, (J. van Leeuwen ed.), vol. B, Elsevier, 1990, pp. 1-53.