Skip to Main content Skip to Navigation
Conference papers

Weakly-unambiguous Parikh automata and their link to holonomic series

Abstract : We investigate the connection between properties of formal languages and properties of their generating series, with a focus on the class of \emph{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.
Complete list of metadatas

https://hal.inria.fr/hal-03084639
Contributor : Alin Bostan <>
Submitted on : Monday, December 21, 2020 - 11:43:48 AM
Last modification on : Monday, January 11, 2021 - 2:59:21 PM

File

LIPIcs-ICALP-2020-114.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03084639, version 1

Collections

Citation

Alin Bostan, Arnaud Carayol, Florent Koechlin, Cyril Nicaud. Weakly-unambiguous Parikh automata and their link to holonomic series. ICALP 2020: The 47th International Colloquium on Automata, Languages and Programming, Jul 2020, Saarbrücken, Germany. pp.16. ⟨hal-03084639⟩

Share

Metrics

Record views

30

Files downloads

223