Florent Koechlin: Generating Functions and Ambiguity in Automata Theory

par Florent Koechlin (LIPN, Paris Nord)

jeudi 5 juin 2025, 11:00 → 12:00 Europe/Paris

Salle Yvette Cauchois (IHP - Bâtiment Perrin)

In the 1980s, Philippe Flajolet elegantly resolved several conjectures on the inherent ambiguity of some context-free languages. The tools he developed rely on the study of the nature of the generating functions associated with these languages, specifically their algebraicity. In this talk, I will present an extension of this approach to a broader class of languages, recognized by Parikh (pushdown) automata.