Florent Koechlin (IRIF, Paris)

Je parlerai de la connexion entre l’intrinsèque ambiguïté en théorie des langages formels et les propriétés des séries génératrices des langages associés. Il est bien connu que les langages réguliers ont des séries génératrices rationnelles et que les séries génératrices des langages algébriques non ambigus sont algébriques. Dans les années 80, Philippe Flajolet a développé plusieurs outils pour prouver facilement et rapidement l’intrinsèque ambiguïté de nombreux langages algébriques à partir de leurs séries génératrices, dont plusieurs résistaient aux techniques historiques de preuve, à base d’itérations.

Dans cet exposé, je présenterai comment ces idées peuvent être généralisées aux automates de Parikh non ambigus, et comment ce lien peut être exploité pour obtenir des bornes de complexité au problème de l’inclusion sur ces automates. Il s’agit d’un travail commun avec Alin Bostan, Arnaud Carayol et Cyril Nicaud.