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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Ronald Graham, Donald Knuth & Oren Patashnik (1994):
Concrete Mathematics,
2nd edition.
Addison Wesley.
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.
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.
John Hopcroft & Jeffrey Ullman (1979):
Introduction to Automata Theory, Languages, and Computation.
Addison-Wesley.
Takumi Kasai & Shigeki Iwata (1992):
Some Problems in Formal Language Theory Known as Decidable are Proved EXPTIME Complete.
RIMS Kokyuroku 796,
pp. 8–21.
Manuel Kauers & Peter Paule (2011):
C-Finite Sequences,
pp. 63–86.
Springer Vienna,
Vienna,
doi:10.1007/978-3-7091-0445-3_4.
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.
Werner Kuich & Arto Salomaa (1986):
Semirings, Automata, Languages.
EATCS Monographs on Theoretical Computer Science 5.
Springer,
doi:10.1007/978-3-642-69959-7.
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.
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.
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.
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.
Stanisław Purgał (2018):
Learning regular languages offline from a positive sample.
University of Warsaw.
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.
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.
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.
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.
Leslie G. Valiant (1975):
Regularity and Related Problems for Deterministic Pushdown Automata.
J. ACM 22(1),
pp. 1–10,
doi:10.1145/321864.321865.
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.
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.