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