Document Open Access Logo

Weakly-Unambiguous Parikh Automata and Their Link to Holonomic Series

Authors Alin Bostan, Arnaud Carayol, Florent Koechlin, Cyril Nicaud

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.114.pdf
  • Filesize: 0.56 MB
  • 16 pages

Document Identifiers

Author Details

Alin Bostan
  • INRIA Saclay Île-de-France, Palaiseau, France
Arnaud Carayol
  • LIGM, Univ. Gustave Eiffel, CNRS, Marne-la-Vallée, France
Florent Koechlin
  • LIGM, Univ. Gustave Eiffel, CNRS, Marne-la-Vallée, France
Cyril Nicaud
  • LIGM, Univ. Gustave Eiffel, CNRS, Marne-la-Vallée, France

Cite AsGet BibTex

Alin Bostan, Arnaud Carayol, Florent Koechlin, and Cyril Nicaud. Weakly-Unambiguous Parikh Automata and Their Link to Holonomic Series. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 114:1-114:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ICALP.2020.114

Abstract

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Formal languages and automata theory
  • Mathematics of computing → Generating functions
Keywords
  • generating series
  • holonomicity
  • ambiguity
  • reversal bounded counter machine
  • Parikh automata

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Jason P. Bell and Shaoshi Chen. Power series with coefficients from a finite set. J. Comb. Theory, Ser. A, 151:241-253, 2017. URL: https://doi.org/10.1016/j.jcta.2017.05.002.
  2. Joseph N. Bernstein. Analytic continuation of generalized functions with respect to a parameter. Funct. Anal. Appl., 6(4):273-28, 1972. URL: https://doi.org/10.1007/BF01077645.
  3. Alin Bostan, Frédéric Chyzak, Grégoire Lecerf, Bruno Salvy, and Éric Schost. Differential equations for algebraic functions. In International Symposium on Symbolic and Algebraic Computation, ISSAC 2007, pages 25-32. ACM, 2007. URL: https://doi.org/10.1145/1277548.1277553.
  4. Mireille Bousquet-Mélou. Rational and algebraic series in combinatorial enumeration. In International Congress of Mathematicians (ICM 2006), volume 3, pages 789-826. Eur. Math. Soc., Zürich, 2006. URL: https://doi.org/10.4171/022-3/40.
  5. Michaël Cadilhac. Automata with a semilinear constraint. PhD thesis, Université de Montréal, 2013. Google Scholar
  6. Michaël Cadilhac, Alain Finkel, and Pierre McKenzie. Affine Parikh automata. RAIRO - Theor. Inf. and Applic., 46(4):511-545, 2012. URL: https://doi.org/10.1051/ita/2012013.
  7. Michaël Cadilhac, Alain Finkel, and Pierre McKenzie. Unambiguous constrained automata. Int. J. Found. Comput. Sci., 24(7):1099-1116, 2013. URL: https://doi.org/10.1142/S0129054113400339.
  8. Giusi Castiglione and Paolo Massazza. On a class of languages with holonomic generating functions. Theor. Comput. Sci., 658:74-84, 2017. URL: https://doi.org/10.1016/j.tcs.2016.07.022.
  9. Dmitry Chistikov and Christoph Haase. The taming of the semi-linear set. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, volume 55 of LIPIcs, pages 128:1-128:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.128.
  10. Noam Chomsky and Marcel-Paul Schützenberger. The Algebraic Theory of Context-Free Languages, volume 35 of Studies in Logic and the Foundations of Mathematics. Elsevier, 1963. URL: https://doi.org/10.1016/S0049-237X(08)72023-8.
  11. Thomas Colcombet. Unambiguity in automata theory. In Jeffrey Shallit and Alexander Okhotin, editors, Descriptional Complexity of Formal Systems - 17th International Workshop, DCFS 2015, Waterloo, ON, Canada, June 25-27, 2015. Proceedings, volume 9118 of Lecture Notes in Computer Science, pages 3-18. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-19225-3_1.
  12. Louis Comtet. Calcul pratique des coefficients de Taylor d'une fonction algébrique. Enseignement Math. (2), 10:267-270, 1964. Google Scholar
  13. Samuel Eilenberg and Marcel-Paul Schützenberger. Rational sets in commutative monoids. J. Algebra, 13(2):173-191, 1969. URL: https://doi.org/10.1016/0021-8693(69)90070-2.
  14. Emmanuel Filiot, Shibashis Guha, and Nicolas Mazzocchi. Two-Way Parikh Automata. In Arkadev Chattopadhyay and Paul Gastin, editors, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019), volume 150 of Leibniz International Proceedings in Informatics (LIPIcs), pages 40:1-40:14, Dagstuhl, Germany, 2019. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2019.40.
  15. Philippe Flajolet. Analytic models and ambiguity of context-free languages. Theor. Comput. Sci., 49(2):283-309, 1987. URL: https://doi.org/10.1016/0304-3975(87)90011-9.
  16. Philippe Flajolet, Stefan Gerhold, and Bruno Salvy. On the non-holonomic character of logarithms, powers, and the nth prime function. Electr. J. Comb., 11(2), 2005. URL: https://doi.org/10.37236/1894.
  17. Philippe Flajolet and Robert Sedgewick. Analytic Combinatorics. Cambridge University Press, first edition, 2009. Google Scholar
  18. Sheila Greibach. A note on undecidable properties of formal languages. Mathematical Systems Theory, 2(1):1-6, 1968. URL: https://doi.org/10.1007/BF01691341.
  19. Oscar H. Ibarra. Reversal-bounded multicounter machines and their decision problems. J. ACM, 25(1):116-133, 1978. URL: https://doi.org/10.1145/322047.322058.
  20. Ryuichi Ito. Every semilinear set is a finite union of disjoint linear sets. J. Comput. Syst. Sci., 3(2):221-231, 1969. URL: https://doi.org/10.1016/S0022-0000(69)80014-0.
  21. Masaki Kashiwara. On the holonomic systems of linear differential equations. II. Invent. Math., 49(2):121-135, 1978. URL: https://doi.org/10.1007/BF01403082.
  22. Manuel Kauers. Bounds for D-finite closure properties. In Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, (ISSAC 2014), pages 288-295. ACM, New York, 2014. URL: https://doi.org/10.1145/2608628.2608634.
  23. Felix Klaedtke and Harald Rueß. Parikh automata and Monadic Second-Order logics with linear cardinality constraints. Technical Report 177, Freiburg University, 2002. Google Scholar
  24. Felix Klaedtke and Harald Rueß. Monadic second-order logics with cardinalities. In Automata, Languages and Programming, 30th International Colloquium, ICALP 2003, volume 2719 of Lecture Notes in Computer Science, pages 681-696. Springer, 2003. URL: https://doi.org/10.1007/3-540-45061-0_54.
  25. Leonard Lipshitz. The diagonal of a D-finite power series is D-finite. J. Algebra, 113(2):373-378, 1988. URL: https://doi.org/10.1016/0021-8693(88)90166-4.
  26. Leonard Lipshitz. D-finite power series. J. Algebra, 122(2):353-373, 1989. URL: https://doi.org/10.1016/0021-8693(89)90222-6.
  27. Paolo Massazza. Holonomic functions and their relation to linearly constrained languages. ITA, 27(2):149-161, 1993. URL: https://doi.org/10.1051/ita/1993270201491.
  28. Paolo Massazza. On the conjecture ℒ_dfcm ⊊ RCM. In Implementation and Application of Automata - 22nd International Conference, CIAA 2017, volume 10329 of Lecture Notes in Computer Science, pages 175-187. Springer, 2017. URL: https://doi.org/10.1007/978-3-319-60134-2_15.
  29. Paolo Massazza. On the generating functions of languages accepted by deterministic one-reversal counter machines. In Proceedings of the 19th Italian Conference on Theoretical Computer Science, (ICTCS 2018), volume 2243 of CEUR Workshop Proceedings, pages 191-202. CEUR-WS.org, 2018. Google Scholar
  30. Rohit J. Parikh. On context-free languages. J. ACM, 13(4):570-581, 1966. URL: https://doi.org/10.1145/321356.321364.
  31. Mojżesz Presburger. Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt. C.R. 1er Congrès des Mathématiciens des pays slaves, pages 92-101, 1929. Google Scholar
  32. Frank P. Ramsey. On a Problem of Formal Logic. Proc. London Math. Soc. (2), 30(4):264-286, 1929. URL: https://doi.org/10.1112/plms/s2-30.1.264.
  33. Richard P. Stanley. Differentiably finite power series. Eur. J. Comb., 1(2):175-188, 1980. URL: https://doi.org/10.1016/S0195-6698(80)80051-5.
  34. Richard P. Stanley. Enumerative combinatorics. Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1999. URL: https://doi.org/10.1017/CBO9780511609589.
  35. Richard Edwin Stearns and Harry B. Hunt III. On the equivalence and containment problems for unambiguous regular expressions, regular grammars and finite automata. SIAM J. Comput., 14(3):598-611, 1985. URL: https://doi.org/10.1137/0214044.
  36. Nobuki Takayama. An approach to the zero recognition problem by Buchberger algorithm. J. Symbolic Comput., 14(2-3):265-282, 1992. URL: https://doi.org/10.1016/0747-7171(92)90039-7.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact