Algorithmes pour l’ambiguïté dans les automates finis

13 octobre 2025

Lê Thành Dũng (Tito) Nguyễn (CNRS, Université Aix-Marseille)

L’ambiguité d’automate fini non-déterministe sur un mot est le nombre d’exécutions acceptantes sur ce mot. Cet exposé présentera des résultats algorithmiques classiques [Weber & Seidl 1986] liés à la croissance asymptotique de l’ambiguïté d’un automate fixé quand le mot d’entrée grandit :

• on peut décider en temps quadratique si un automate est non ambigu ;
• tout automate est forcément soit polynomialement ambigu soit exponentiellement ambigu, et on peut déterminer en temps quadratique dans quel cas on est ;
• dans le cas polynomial, on peut calculer le degré du polynôme en temps cubique.

(J’ai récemment étendu ces résultats aux automates d’arbres dans un travail avec Gallot et Lhote https://arxiv.org/abs/2501.10270 ; et un autre article récent de Drabik et al. https://arxiv.org/abs/2501.14725 montre que les complexités sont optimales.)