Weakly-unambiguous Parikh automata and their link to holonomic series
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911315482640384 |
|---|---|
| author | Bostan, Alin Carayol, Arnaud Koechlin, Florent Nicaud, Cyril |
| author_facet | Bostan, Alin Carayol, Arnaud Koechlin, Florent Nicaud, Cyril |
| contents | 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 to its complexity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_09823 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Weakly-unambiguous Parikh automata and their link to holonomic series Bostan, Alin Carayol, Arnaud Koechlin, Florent Nicaud, Cyril Formal Languages and Automata Theory Symbolic Computation 68Q45 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 to its complexity. |
| title | Weakly-unambiguous Parikh automata and their link to holonomic series |
| topic | Formal Languages and Automata Theory Symbolic Computation 68Q45 |
| url | https://arxiv.org/abs/2512.09823 |