2026-07-24T08:09:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12521 2024-03-06T10:50:21Z ddc:004 open_access

Weakly-Unambiguous Parikh Automata and Their Link to Holonomic Series Bostan, Alin Carayol, Arnaud Koechlin, Florent Nicaud, Cyril generating series holonomicity ambiguity reversal bounded counter machine Parikh automata We investigate the connection between properties of formal languages and properties of their generating series, with a focus on the class of holonomic power series. We first prove a strong version of a conjecture by Castiglione and Massazza: weakly-unambiguous Parikh automata are equivalent to unambiguous two-way reversal bounded counter machines, and their multivariate generating series are holonomic. We then show that the converse is not true: we construct a language whose generating series is algebraic (thus holonomic), but which is inherently weakly-ambiguous as a Parikh automata language. Finally, we prove an effective decidability result for the inclusion problem for weakly-unambiguous Parikh automata, and provide an upper-bound on its complexity. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alin Bostan and Arnaud Carayol and Florent Koechlin and Cyril Nicaud 2020 Is Part Of LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2020.114 urn:nbn:de:0030-drops-125212 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.114 eng https://creativecommons.org/licenses/by/3.0/legalcode