References

  1. Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen & Peter Bro Miltersen (2009): On the Complexity of Numerical Analysis. SIAM J. Comput. 38(5), pp. 1987–2006, doi:10.1137/070697926.
  2. Marti Soittola Arto Salomaa (1978): Automata-theoretic aspects of formal power series. Texts and Monographs in Computer Science. Springer, doi:10.1007/978-1-4612-6264-0.
  3. Corentin Barloy, Nathanaël Fijalkow, Nathan Lhote & Filip Mazowiecki (2020): A Robust Class of Linear Recurrence Sequences. In: Maribel Fernández & Anca Muscholl: 28th EACSL Annual Conference on Computer Science Logic (CSL 2020), Leibniz International Proceedings in Informatics (LIPIcs) 152. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, pp. 9:1–9:16, doi:10.4230/LIPIcs.CSL.2020.9.
  4. Mikołaj Bojańczyk, Bartek Klin & Sławomir Lasota (2014): Automata theory in nominal sets. Logical Methods in Computer Science Volume 10, Issue 3, doi:10.2168/LMCS-10(3:4)2014.
  5. Alin Bostan, Arnaud Carayol, Florent Koechlin & Cyril Nicaud (2020): Weakly-unambiguous Parikh automata and their link to holonomic series. In: Accepted for publication in ICALP'20.
  6. Michaël Cadilhac, Filip Mazowiecki, Charles Paperman, MichałPilipczuk & Géraud Sénizergues (2020): On polynomial recursive sequences. In: Accepted for publication in ICALP'20.
  7. John Canny (1988): Some Algebraic and Geometric Computations in PSPACE. In: Proc. of STOC '88. ACM, New York, NY, USA, pp. 460–467, doi:10.1145/62212.62257.
  8. N. Chomsky & M. P. Schützenberger (1963): The Algebraic Theory of Context-Free Languages. In: P. Braffort & D. Hirschberg: Computer Programming and Formal Systems, Studies in Logic and the Foundations of Mathematics 35. Elsevier, pp. 118–161, doi:10.1016/S0049-237X(08)72023-8.
  9. Lorenzo Clemente (2020): On the complexity of the universality and inclusion problems for unambiguous context-free grammars (Invited Paper). arXiv e-prints arXiv:2006.05275. Available at https://arxiv.org/abs/2006.05275.
  10. Wojciech Czerwiński, Diego Figueira & Piotr Hofman (2020): Universality Problem for Unambiguous VASS. Available at https://hal.archives-ouvertes.fr/hal-02483495. Working paper or preprint.
  11. Wojciech Czerwinski, Slawomir Lasota, Roland Meyer, Sebastian Muskalla, K. Narayan Kumar & Prakash Saivasan (2018): Regular Separability of Well-Structured Transition Systems. In: Sven Schewe & Lijun Zhang: Proc. of CONCUR'18, Leibniz International Proceedings in Informatics (LIPIcs) 118. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, pp. 35:1–35:18, doi:10.4230/LIPIcs.CONCUR.2018.35.
  12. Volker Diekert & Steffen Kopecki (2010): Complexity Results and the Growths of Hairpin Completions of Regular Languages. In: Proc. of CIAA'10, CIAA'10. Springer-Verlag, Berlin, Heidelberg, pp. 105–114, doi:10.1007/978-3-642-18098-9_12.
  13. Javier Esparza, Andreas Gaiser & Stefan Kiefer (2010): Computing Least Fixed Points of Probabilistic Systems of Polynomials. In: Jean-Yves Marion & Thomas Schwentick: STACS'10, Leibniz International Proceedings in Informatics (LIPIcs) 5. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, pp. 359–370, doi:10.4230/LIPIcs.STACS.2010.2468.
  14. Kousha Etessami, Alistair Stewart & Mihalis Yannakakis (2013): Stochastic Context-free Grammars, Regular Languages, and Newton's Method. In: In Proc. of ICALP'13, ICALP'13. Springer-Verlag, Berlin, Heidelberg, pp. 199–211, doi:10.1007/978-3-642-39212-2_20.
  15. Kousha Etessami & Mihalis Yannakakis (2009): Recursive Markov Chains, Stochastic Grammars, and Monotone Systems of Nonlinear Equations. J. ACM 56(1), pp. 1:1–1:66, doi:10.1145/1462153.1462154.
  16. Vojtěch Forejt, Petr Jančar, Stefan Kiefer & James Worrell (2014): Language equivalence of probabilistic pushdown automata. Information and Computation 237, pp. 1–11, doi:10.1016/j.ic.2014.04.003.
  17. Ronald Graham, Donald Knuth & Oren Patashnik (1994): Concrete Mathematics, 2nd edition. Addison Wesley.
  18. D. Yu Grigor'ev (1988): Complexity of deciding Tarski algebra. Journal of Symbolic Computation 5(1), pp. 65–108, doi:10.1016/S0747-7171(88)80006-3.
  19. Thomas N. Hibbard & Joseph Ullian (1966): The Independence of Inherent Ambiguity From Complementedness Among Context-Free Languages. J. ACM 13(4), pp. 588–593, doi:10.1145/321312.321318.
  20. John Hopcroft & Jeffrey Ullman (1979): Introduction to Automata Theory, Languages, and Computation. Addison-Wesley.
  21. Takumi Kasai & Shigeki Iwata (1992): Some Problems in Formal Language Theory Known as Decidable are Proved EXPTIME Complete. RIMS Kokyuroku 796, pp. 8–21.
  22. Manuel Kauers & Peter Paule (2011): C-Finite Sequences, pp. 63–86. Springer Vienna, Vienna, doi:10.1007/978-3-7091-0445-3_4.
  23. Werner Kuich (1994): On the Multiplicity Equivalence Problem for Context-Free Grammars. In: Proceedings of the Colloquium in Honor of Arto Salomaa on Results and Trends in Theoretical Computer Science. Springer-Verlag, Berlin, Heidelberg, pp. 232—250, doi:10.1007/3-540-58131-6_50.
  24. Werner Kuich & Arto Salomaa (1986): Semirings, Automata, Languages. EATCS Monographs on Theoretical Computer Science 5. Springer, doi:10.1007/978-3-642-69959-7.
  25. B. Litow (1996): Bounded length UCFG equivalence. In: Tetsuo Asano, Yoshihide Igarashi, Hiroshi Nagamochi, Satoru Miyano & Subhash Suri: Algorithms and Computation. Springer Berlin Heidelberg, Berlin, Heidelberg, pp. 239–246, doi:10.1007/BFb0009500.
  26. P. Massazza & N. Sabadini (1989): Some applications and techniques for generating functions. In: Josep Díaz & Fernando Orejas: TAPSOFT '89. Springer Berlin Heidelberg, Berlin, Heidelberg, pp. 321–336, doi:10.1007/3-540-50939-9_141.
  27. A. R. Meyer & L. J. Stockmeyer (1972): The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space. In: Proceedings of the 13th Annual Symposium on Switching and Automata Theory, SWAT '72. IEEE Computer Society, Washington, DC, USA, pp. 125–129, doi:10.1109/SWAT.1972.29.
  28. Antoine Mottet & Karin Quaas (2019): The Containment Problem for Unambiguous Register Automata. In: Rolf Niedermeier & Christophe Paul: Proc. of STACS'19, Leibniz International Proceedings in Informatics (LIPIcs) 126. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany, pp. 53:1–53:15, doi:10.4230/LIPIcs.STACS.2019.53.
  29. Stanisław Purgał (2018): Learning regular languages offline from a positive sample. University of Warsaw.
  30. Géraud Sénizergues (1997): The equivalence problem for deterministic pushdown automata is decidable. In: Pierpaolo Degano, Roberto Gorrieri & Alberto Marchetti-Spaccamela: Proc. of ICALP'97. Springer Berlin Heidelberg, Berlin, Heidelberg, pp. 671–681, doi:10.1007/3-540-63165-8_221.
  31. Priti Shankar & B. S. Adiga (1991): A Graph-based Regularity Test for Deterministic Context-free Languages. Theor. Comput. Sci. 88(1), pp. 117–125, doi:10.1016/0304-3975(91)90076-E.
  32. R.E. Stearns (1967): A regularity test for pushdown machines. Information and Control 11(3), pp. 323 – 340, doi:10.1016/S0019-9958(67)90591-8.
  33. Richard E. Stearns & Harry B. Hunt (1981): On the equivalence and containment problems for unambiguous regular expressions, grammars, and automata. In: Proceedings of the 22nd Annual Symposium on Foundations of Computer Science, SFCS '81. IEEE Computer Society, Washington, DC, USA, pp. 74–81, doi:10.1109/SFCS.1981.29.
  34. Leslie G. Valiant (1975): Regularity and Related Problems for Deterministic Pushdown Automata. J. ACM 22(1), pp. 1–10, doi:10.1145/321864.321865.
  35. Tzeng Wen-Guey (1996): On path equivalence of nondeterministic finite automata. Information Processing Letters 58(1), pp. 43–46, doi:10.1016/0020-0190(96)00039-7.
  36. Doron Zeilberger (1990): A holonomic systems approach to special functions identities. Journal of Computational and Applied Mathematics 32(3), pp. 321–368, doi:10.1016/0377-0427(90)90042-X.

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org