Weakly unambiguous Parikh automata and their link to holonomic series

Mar 28 11:00 ₂₀₂₂

Abstract: I will talk about the connection between inherent ambiguity of formal languages and the properties of their generating series. It is a classical result that regular languages have rational generating series and that the generating series of unambiguous context-free languages are algebraic. In the eighties, Philippe Flajolet developed several tools based on this connection to prove efficiently and easily the inherent ambiguity of many context-free languages, some of which resisted the historical methods based on iterations.

In this talk I will present how these ideas relying on generating series can be extended to Parikh automata, and how they provide an algorithmic tool to decide the inclusion problem for weakly unambiguous Parikh automata. This is a joint work with Alin Bostan, Arnaud Carayol and Cyril Nicaud.