{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T08:53:10Z","timestamp":1770281590925,"version":"3.49.0"},"publisher-location":"Cham","reference-count":58,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031308284","type":"print"},{"value":"9783031308291","type":"electronic"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,4,21]],"date-time":"2023-04-21T00:00:00Z","timestamp":1682035200000},"content-version":"vor","delay-in-days":110,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider a general class of decision problems concerning formal languages, called \u201c(one-dimensional) unboundedness predicates\u201d, for automata that feature reversal-bounded counters (RBCA). We show that each problem in this class reduces\u2014non-deterministically in polynomial time\u2014to the same problem for just finite automata. We also show an analogous reduction for automata that have access to both a pushdown stack and reversal-bounded counters (PRBCA).<\/jats:p><jats:p>This allows us to answer several open questions: For example, we show that it is<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\textsf{coNP}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>coNP<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-complete to decide whether a given (P)RBCA language<jats:italic>L<\/jats:italic>is bounded, meaning whether there exist words<jats:inline-formula><jats:alternatives><jats:tex-math>$$w_1,\\ldots ,w_n$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:msub><mml:mi>w<\/mml:mi><mml:mn>1<\/mml:mn><\/mml:msub><mml:mo>,<\/mml:mo><mml:mo>\u2026<\/mml:mo><mml:mo>,<\/mml:mo><mml:msub><mml:mi>w<\/mml:mi><mml:mi>n<\/mml:mi><\/mml:msub><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>with<jats:inline-formula><jats:alternatives><jats:tex-math>$$L\\subseteq w_1^*\\cdots w_n^*$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>L<\/mml:mi><mml:mo>\u2286<\/mml:mo><mml:msubsup><mml:mi>w<\/mml:mi><mml:mn>1<\/mml:mn><mml:mo>\u2217<\/mml:mo><\/mml:msubsup><mml:mo>\u22ef<\/mml:mo><mml:msubsup><mml:mi>w<\/mml:mi><mml:mi>n<\/mml:mi><mml:mo>\u2217<\/mml:mo><\/mml:msubsup><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. For PRBCA, even decidability was open. Our methods also show that there is no language of a (P)RBCA of intermediate growth. This means, the number of words of each length grows either polynomially or exponentially. Part of our proof is likely of independent interest: We show that one can translate an RBCA into a machine with<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathbb {Z}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>Z<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-counters in logarithmic space, while preserving the accepted language.<\/jats:p>","DOI":"10.1007\/978-3-031-30829-1_12","type":"book-chapter","created":{"date-parts":[[2023,4,20]],"date-time":"2023-04-20T19:56:19Z","timestamp":1682020579000},"page":"240-264","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Unboundedness Problems for Machines with Reversal-Bounded Counters"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9371-0807","authenticated-orcid":false,"given":"Pascal","family":"Baumann","sequence":"first","affiliation":[]},{"given":"Flavio","family":"D\u2019Alessandro","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0775-7781","authenticated-orcid":false,"given":"Moses","family":"Ganardi","sequence":"additional","affiliation":[]},{"given":"Oscar","family":"Ibarra","sequence":"additional","affiliation":[]},{"given":"Ian","family":"McQuillan","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4002-5491","authenticated-orcid":false,"given":"Lia","family":"Sch\u00fctze","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6421-4388","authenticated-orcid":false,"given":"Georg","family":"Zetzsche","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,4,21]]},"reference":[{"key":"12_CR1","unstructured":"Alfred V. Aho and Jeffrey D. Ullman. The theory of parsing, translation, and compiling. 1: Parsing. Prentice-Hall, 1972. isbn: 0139145567. url: https:\/\/www.worldcat.org\/oclc\/310805937."},{"key":"12_CR2","doi-asserted-by":"publisher","unstructured":"Brenda S Baker and Ronald V Book. \u201cReversal-bounded multipushdown machines\u201d. In: Journal of Computer and System Sciences 8.3 (1974), pp. 315\u2013332. doi: https:\/\/doi.org\/10.1016\/S0022-0000(74)80027-9.","DOI":"10.1016\/S0022-0000(74)80027-9"},{"key":"12_CR3","doi-asserted-by":"publisher","unstructured":"David Barozzini, Lorenzo Clemente, Thomas Colcombet, and Pawel Parys. \u201cCost Automata, Safe Schemes, and Downward Closures\u201d. In: 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbr\u00fccken, Germany (Virtual Conference). Ed. by Artur Czumaj, Anuj Dawar, and Emanuela Merelli. Vol. 168. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2020, 109:1\u2013109:18. doi: https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2020.109.","DOI":"10.4230\/LIPIcs.ICALP.2020.109"},{"key":"12_CR4","doi-asserted-by":"publisher","unstructured":"David Barozzini, Pawel Parys, and Jan Wroblewski. \u201cUnboundedness for Recursion Schemes: A Simpler Type System\u201d. In: 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France. Ed. by Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff. Vol. 229. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2022, 112:1\u2013112:19. doi: https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2022.112.","DOI":"10.4230\/LIPIcs.ICALP.2022.112"},{"key":"12_CR5","doi-asserted-by":"publisher","unstructured":"Pascal Baumann, Flavio D\u2019Alessandro, Moses Ganardi, Oscar Ibarra, Ian McQuillan, Lia Sch\u00fctze, and Georg Zetzsche. Unboundedness problems for machines with reversal-bounded counters. 2023. doi: https:\/\/doi.org\/10.48550\/ARXIV.2301.10198. url: https:\/\/arxiv.org\/abs\/2301.10198.","DOI":"10.48550\/ARXIV.2301.10198"},{"key":"12_CR6","doi-asserted-by":"publisher","unstructured":"Alin Bostan, Arnaud Carayol, Florent Koechlin, and Cyril Nicaud. \u201cWeakly-Unambiguous Parikh Automata and Their Link to Holonomic Series\u201d. In: 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbr\u00fccken, Germany (Virtual Conference). Vol. 168. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2020, 114:1\u2013114:16. doi: https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2020.114.","DOI":"10.4230\/LIPIcs.ICALP.2020.114"},{"key":"12_CR7","doi-asserted-by":"publisher","unstructured":"Toby Cathcart Burn, Luke Ong, Steven J. Ramsay, and Dominik Wagner. \u201cInitial Limit Datalog: a New Extensible Class of Decidable Constrained Horn Clauses\u201d. In: 36th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2021, Rome, Italy, June 29 - July 2, 2021. IEEE, 2021, pp. 1\u201313. doi: https:\/\/doi.org\/10.1109\/LICS52264.2021.9470527.","DOI":"10.1109\/LICS52264.2021.9470527"},{"key":"12_CR8","doi-asserted-by":"publisher","unstructured":"Micha\u00ebl Cadilhac, Alain Finkel, and Pierre McKenzie. \u201cAffine Parikh automata\u201d. In: RAIRO Theor. Informatics Appl. 46.4 (2012), pp. 511\u2013545. doi: https:\/\/doi.org\/10.1051\/ita\/2012013.","DOI":"10.1051\/ita\/2012013"},{"key":"12_CR9","doi-asserted-by":"publisher","unstructured":"Micha\u00ebl Cadilhac, Alain Finkel, and Pierre McKenzie. \u201cBounded Parikh Automata\u201d. In: Int. J. Found. Comput. Sci. 23.8 (2012), pp. 1691\u20131710. doi: https:\/\/doi.org\/10.1142\/S0129054112400709.","DOI":"10.1142\/S0129054112400709"},{"key":"12_CR10","doi-asserted-by":"publisher","unstructured":"Micha\u00ebl Cadilhac, Andreas Krebs, and Pierre McKenzie. \u201cThe Algebraic Theory of Parikh Automata\u201d. In: Theory Comput. Syst. 62.5 (2018), pp. 1241\u20131268. doi: https:\/\/doi.org\/10.1007\/s00224-017-9817-2.","DOI":"10.1007\/s00224-017-9817-2"},{"key":"12_CR11","doi-asserted-by":"publisher","unstructured":"Arturo Carpi, Flavio D\u2019Alessandro, Oscar\u00a0H Ibarra, and Ian McQuillan. \u201cRelationships between bounded languages, counter machines, finite-index grammars, ambiguity, and commutative regularity\u201d. In: Theoretical Computer Science 862 (2021), pp. 97\u2013118. doi: https:\/\/doi.org\/10.1016\/j.tcs.2020.10.006.","DOI":"10.1016\/j.tcs.2020.10.006"},{"key":"12_CR12","doi-asserted-by":"publisher","unstructured":"Tat-hung Chan. \u201cPushdown Automata with Reversal-Bounded Counters\u201d. In: J. Comput. Syst. Sci. 37.3 (1988), pp. 269\u2013291. doi: https:\/\/doi.org\/10.1016\/0022-0000(88)90008-6.","DOI":"10.1016\/0022-0000(88)90008-6"},{"key":"12_CR13","doi-asserted-by":"publisher","unstructured":"Lorenzo Clemente, Wojciech Czerwinski, Slawomir Lasota, and Charles Paperman. \u201cRegular Separability of Parikh Automata\u201d. In: 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland. Vol. 80. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2017, 117:1\u2013117:13. doi: https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2017.117.","DOI":"10.4230\/LIPIcs.ICALP.2017.117"},{"key":"12_CR14","doi-asserted-by":"publisher","unstructured":"Lorenzo Clemente, Pawel Parys, Sylvain Salvati, and Igor Walukiewicz. \u201cThe Diagonal Problem for Higher-Order Recursion Schemes is Decidable\u201d. In: Proceedings of the 31st Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS \u201916, New York, NY, USA, July 5-8, 2016. Ed. by Martin Grohe, Eric Koskinen, and Natarajan Shankar. ACM, 2016, pp. 96\u2013105. doi: https:\/\/doi.org\/10.1145\/2933575.2934527.","DOI":"10.1145\/2933575.2934527"},{"key":"12_CR15","doi-asserted-by":"publisher","unstructured":"Wojciech Czerwinski, Piotr Hofman, and Georg Zetzsche. \u201cUnboundedness Problems for Languages of Vector Addition Systems\u201d. In: 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic. Ed. by Ioannis Chatzigiannakis, Christos Kaklamanis, D\u00e1niel Marx, and Donald Sannella. Vol. 107. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2018, 119:1\u2013119:15. doi: https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2018.119.","DOI":"10.4230\/LIPIcs.ICALP.2018.119"},{"key":"12_CR16","doi-asserted-by":"publisher","unstructured":"Flavio D\u2019Alessandro and Benedetto Intrigila. \u201cOn the commutative equivalence of bounded context-free and regular languages: The semi-linear case\u201d. In: Theor. Comput. Sci. 572 (2015), pp. 1\u201324. doi: https:\/\/doi.org\/10.1016\/j.tcs.2015.01.008. url: https:\/\/doi.org\/10.1016\/j.tcs.2015.01.008.","DOI":"10.1016\/j.tcs.2015.01.008"},{"key":"12_CR17","doi-asserted-by":"publisher","unstructured":"Joey Eremondi, Oscar H. Ibarra, and Ian McQuillan. \u201cOn the Density of Context-Free and Counter Languages\u201d. In: Developments in Language Theory - 19th International Conference, DLT 2015, Liverpool, UK, July 27-30, 2015, Proceedings. Ed. by Igor Potapov. Vol. 9168. Lecture Notes in Computer Science. Springer, 2015, pp. 228\u2013239. doi: https:\/\/doi.org\/10.1007\/978-3-319-21500-6_18.","DOI":"10.1007\/978-3-319-21500-6_18"},{"key":"12_CR18","doi-asserted-by":"publisher","unstructured":"Joey Eremondi, Oscar H. Ibarra, and Ian McQuillan. \u201cOn the Density of Context-Free and Counter Languages\u201d. In: Int. J. Found. Comput. Sci. 29.2 (2018), pp. 233\u2013250. doi: https:\/\/doi.org\/10.1142\/S0129054118400051.","DOI":"10.1142\/S0129054118400051"},{"key":"12_CR19","doi-asserted-by":"crossref","unstructured":"Javier Esparza. \u201cPetri nets, commutative context-free grammars, and basic parallel processes\u201d. In: Fundamenta Informaticae 31.1 (1997), pp. 13\u201325.","DOI":"10.3233\/FI-1997-3112"},{"key":"12_CR20","doi-asserted-by":"publisher","unstructured":"Javier Esparza, Pierre Ganty, and Rupak Majumdar. \u201cA Perfect Model for Bounded Verification\u201d. In: Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science, LICS 2012, Dubrovnik, Croatia, June 25-28, 2012. IEEE Computer Society, 2012, pp. 285\u2013294. doi: https:\/\/doi.org\/10.1109\/LICS.2012.39.","DOI":"10.1109\/LICS.2012.39"},{"key":"12_CR21","doi-asserted-by":"publisher","unstructured":"Henning Fernau and Ralf Stiebe. \u201cSequential grammars and automata with valences\u201d. In: Theor. Comput. Sci. 276.1-2 (2002), pp. 377\u2013405. doi: https:\/\/doi.org\/10.1016\/S0304-3975(01)00282-1.","DOI":"10.1016\/S0304-3975(01)00282-1"},{"key":"12_CR22","doi-asserted-by":"publisher","unstructured":"Emmanuel Filiot, Shibashis Guha, and Nicolas Mazzocchi. \u201cTwo-Way Parikh Automata\u201d. In: 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2019, December 11-13, 2019, Bombay, India. Vol. 150. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2019, 40:1\u201340:14. doi: https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2019.40.","DOI":"10.4230\/LIPIcs.FSTTCS.2019.40"},{"key":"12_CR23","doi-asserted-by":"publisher","unstructured":"Alain Finkel and Arnaud Sangnier. \u201cReversal-Bounded Counter Machines Revisited\u201d. In: Mathematical Foundations of Computer Science 2008, 33rd International Symposium, MFCS 2008, Torun, Poland, August 25-29, 2008, Proceedings. Ed. by Edward Ochmanski and Jerzy Tyszkiewicz. Vol. 5162. Lecture Notes in Computer Science. Springer, 2008, pp. 323\u2013334. doi: https:\/\/doi.org\/10.1007\/978-3-540-85238-4_26.","DOI":"10.1007\/978-3-540-85238-4_26"},{"key":"12_CR24","doi-asserted-by":"publisher","unstructured":"Pawel Gawrychowski, Dalia Krieger, Narad Rampersad, and Jeffrey O. Shallit. \u201cFinding the Growth Rate of a Regular or Context-Free Language in Polynomial Time\u201d. In: Int. J. Found. Comput. Sci. 21.4 (2010), pp. 597\u2013618. doi: https:\/\/doi.org\/10.1142\/S0129054110007441.","DOI":"10.1142\/S0129054110007441"},{"key":"12_CR25","doi-asserted-by":"crossref","unstructured":"Seymour Ginsburg and Edwin H Spanier. \u201cBounded ALGOL-like languages\u201d. In: Transactions of the American Mathematical Society 113.2 (1964), pp. 333\u2013368.","DOI":"10.1090\/S0002-9947-1964-0181500-1"},{"key":"12_CR26","doi-asserted-by":"publisher","unstructured":"Sheila A. Greibach. \u201cRemarks on Blind and Partially Blind One-Way Multicounter Machines\u201d. In: Theor. Comput. Sci. 7 (1978), pp. 311\u2013324. doi: https:\/\/doi.org\/10.1016\/0304-3975(78)90020-8.","DOI":"10.1016\/0304-3975(78)90020-8"},{"key":"12_CR27","doi-asserted-by":"crossref","unstructured":"Rostislav Grigorchuk and A. Mach\u00ec. \u201cAn example of an indexed language of intermediate growth\u201d. In: Theoretical computer science 215.1-2 (1999), pp. 325\u2013327.","DOI":"10.1016\/S0304-3975(98)00161-3"},{"key":"12_CR28","doi-asserted-by":"publisher","unstructured":"Eitan M. Gurari and Oscar H. Ibarra. \u201cThe complexity of decision problems for finite-turn multicounter machines\u201d. In: Journal of Computer and System Sciences 22.2 (1981), pp. 220\u2013229. issn: 0022-0000. doi: https:\/\/doi.org\/10.1016\/0022-0000(81)90028-3.","DOI":"10.1016\/0022-0000(81)90028-3"},{"key":"12_CR29","doi-asserted-by":"publisher","unstructured":"Christoph Haase and Simon Halfon. \u201cInteger Vector Addition Systems with States\u201d. In: Reachability Problems - 8th International Workshop, RP 2014, Oxford, UK, September 22-24, 2014. Proceedings. Ed. by Jo\u00ebl Ouaknine, Igor Potapov, and James Worrell. Vol. 8762. Lecture Notes in Computer Science. Springer, 2014, pp. 112\u2013124. doi: https:\/\/doi.org\/10.1007\/978-3-319-11439-2_9.","DOI":"10.1007\/978-3-319-11439-2_9"},{"key":"12_CR30","doi-asserted-by":"publisher","unstructured":"Christoph Haase and Georg Zetzsche. \u201cPresburger arithmetic with stars, rational subsets of graph groups, and nested zero tests\u201d. In: 34th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2019, Vancouver, BC, Canada, June 24-27, 2019. IEEE, 2019, pp. 1\u201314. doi: https:\/\/doi.org\/10.1109\/LICS.2019.8785850. url: https:\/\/doi.org\/10.1109\/LICS.2019.8785850.","DOI":"10.1109\/LICS.2019.8785850 10.1109\/LICS.2019.8785850"},{"key":"12_CR31","doi-asserted-by":"publisher","unstructured":"Matthew Hague, Jonathan Kochems, and C.-H. Luke Ong. \u201cUnboundedness and downward closures of higher-order pushdown automata\u201d. In: Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2016, St. Petersburg, FL, USA, January 20 - 22, 2016. ACM, 2016, pp. 151\u2013163. doi: https:\/\/doi.org\/10.1145\/2837614.2837627.","DOI":"10.1145\/2837614.2837627"},{"key":"12_CR32","doi-asserted-by":"publisher","unstructured":"Matthew Hague and Anthony Widjaja Lin. \u201cModel Checking Recursive Programs with Numeric Data Types\u201d. In: Computer Aided Verification -23rd International Conference, CAV 2011, Snowbird, UT, USA, July 14-20, 2011. Proceedings. Ed. by Ganesh Gopalakrishnan and Shaz Qadeer. Vol. 6806. Lecture Notes in Computer Science. Springer, 2011, pp. 743\u2013759. doi: https:\/\/doi.org\/10.1007\/978-3-642-22110-1_60.","DOI":"10.1007\/978-3-642-22110-1_60"},{"key":"12_CR33","doi-asserted-by":"publisher","unstructured":"Simon Halfon, Philippe Schnoebelen, and Georg Zetzsche. \u201cDecidability, complexity, and expressiveness of first-order logic over the subword ordering\u201d. In: 32nd Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2017, Reykjavik, Iceland, June 20-23, 2017. IEEE Computer Society, 2017, pp. 1\u201312. doi: https:\/\/doi.org\/10.1109\/LICS.2017.8005141.","DOI":"10.1109\/LICS.2017.8005141"},{"key":"12_CR34","doi-asserted-by":"publisher","unstructured":"Takeshi Hayashi. \u201cOn Derivation Trees of Indexed Grammars\u2014An Extension of the uvwxy-Theorem\u201d. In: Publications of the Research Institute for Mathematical Sciences 9.1 (1973), pp. 61\u201392. doi: https:\/\/doi.org\/10.2977\/prims\/1195192738.","DOI":"10.2977\/prims\/1195192738"},{"key":"12_CR35","doi-asserted-by":"crossref","unstructured":"John E. Hopcroft. \u201cOn the equivalence and containment problems for context-free languages\u201d. In: Mathematical systems theory 3.2 (1969), pp. 119\u2013124.","DOI":"10.1007\/BF01746517"},{"key":"12_CR36","doi-asserted-by":"publisher","unstructured":"Oscar H. Ibarra. \u201cReversal-Bounded Multicounter Machines and Their Decision Problems\u201d. In: J. ACM 25.1 (1978), pp. 116\u2013133. doi: https:\/\/doi.org\/10.1145\/322047.322058.","DOI":"10.1145\/322047.322058"},{"key":"12_CR37","doi-asserted-by":"publisher","unstructured":"Oscar H. Ibarra and Bala Ravikumar. \u201cOn Sparseness, Ambiguity and other Decision Problems for Acceptors and Transducers\u201d. In: STACS 86, 3rd Annual Symposium on Theoretical Aspects of Computer Science, Orsay, France, January 16-18, 1986, Proceedings. Ed. by Burkhard Monien and Guy Vidal-Naquet. Vol. 210. Lecture Notes in Computer Science. Springer, 1986, pp. 171\u2013179. doi: https:\/\/doi.org\/10.1007\/3-540-16078-7_74.","DOI":"10.1007\/3-540-16078-7_74"},{"key":"12_CR38","doi-asserted-by":"publisher","unstructured":"Oscar H. Ibarra and Shinnosuke Seki. \u201cCharacterizations of Bounded semilinear Languages by One-Way and Two-Way Deterministic Machines\u201d. In: Int. J. Found. Comput. Sci. 23.6 (2012), pp. 1291\u20131306. doi: https:\/\/doi.org\/10.1142\/S0129054112400539.","DOI":"10.1142\/S0129054112400539"},{"key":"12_CR39","doi-asserted-by":"publisher","unstructured":"Oscar H. Ibarra, Jianwen Su, Zhe Dang, Tevfik Bultan, and Richard A. Kemmerer. \u201cCounter Machines and Verification Problems\u201d. In: Theor. Comput. Sci. 289.1 (2002), pp. 165\u2013189. doi: https:\/\/doi.org\/10.1016\/S0304-3975(01)00268-7.","DOI":"10.1016\/S0304-3975(01)00268-7"},{"key":"12_CR40","doi-asserted-by":"publisher","unstructured":"Matthias Jantzen and Alexy Kurganskyy. \u201cRefining the hierarchy of blind multicounter languages and twist-closed trios\u201d. In: Inf. Comput. 185.2 (2003), pp. 159\u2013181. doi: https:\/\/doi.org\/10.1016\/S0890-5401(03)00087-7.","DOI":"10.1016\/S0890-5401(03)00087-7"},{"key":"12_CR41","doi-asserted-by":"crossref","unstructured":"Felix Klaedtke and Harald Rue\u00df. \u201cMonadic Second-Order Logics with Cardinalities\u201d. In: Proceedings of ICALP 2003. Ed. by Jos C. M. Baeten, Jan Karel Lenstra, Joachim Parrow, and Gerhard J. Woeginger. Berlin, Heidelberg: Springer, 2003, pp. 681\u2013696.","DOI":"10.1007\/3-540-45061-0_54"},{"key":"12_CR42","doi-asserted-by":"publisher","unstructured":"Naoki Kobayashi. \u201cInclusion between the frontier language of a non-deterministic recursive program scheme and the Dyck language is undecidable\u201d. In: Theor. Comput. Sci. 777 (2019), pp. 409\u2013416. doi: https:\/\/doi.org\/10.1016\/j.tcs.2018.09.035.","DOI":"10.1016\/j.tcs.2018.09.035"},{"key":"12_CR43","doi-asserted-by":"crossref","unstructured":"S. Rao Kosaraju. \u201cDecidability of Reachability in Vector Addition Systems (Preliminary Version)\u201d. In: STOC 1982, May 5-7, 1982, San Francisco, California, USA. 1982, pp. 267\u2013281.","DOI":"10.1145\/800070.802201"},{"key":"12_CR44","unstructured":"Manfred Kufleitner. Yet another proof of Parikh\u2019s Theorem. Oct. 6, 2022. arXiv: 2210.02925."},{"key":"12_CR45","doi-asserted-by":"publisher","unstructured":"Dietrich Kuske and Georg Zetzsche. \u201cLanguages Ordered by the Subword Order\u201d. In: Foundations of Software Science and Computation Structures - 22nd International Conference, FOSSACS 2019, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2019, Prague, Czech Republic, April 6-11, 2019, Proceedings. Ed. by Mikolaj Bojanczyk and Alex Simpson. Vol. 11425. Lecture Notes in Computer Science. Springer, 2019, pp. 348\u2013364. doi: https:\/\/doi.org\/10.1007\/978-3-030-17127-8_20.","DOI":"10.1007\/978-3-030-17127-8_20"},{"key":"12_CR46","doi-asserted-by":"crossref","unstructured":"Jean-Luc Lambert. \u201cA Structure to Decide Reachability in Petri Nets\u201d. In: Theor. Comput. Sci. 99.1 (1992), pp. 79\u2013104.","DOI":"10.1016\/0304-3975(92)90173-D"},{"key":"12_CR47","unstructured":"J\u00e9r\u00f4me Leroux, M. Praveen, Philippe Schnoebelen, and Gr\u00e9goire Sutre. \u201cOn Functions Weakly Computable by Pushdown Petri Nets and Related Systems\u201d. In: CoRR abs\/1904.04090 (2019). arXiv: 1904.04090."},{"key":"12_CR48","doi-asserted-by":"publisher","unstructured":"J\u00e9r\u00f4me Leroux and Sylvain Schmitz. \u201cDemystifying Reachability in Vector Addition Systems\u201d. In: 30th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2015, Kyoto, Japan, July 6-10, 2015. IEEE Computer Society, 2015, pp. 56\u201367. doi: https:\/\/doi.org\/10.1109\/LICS.2015.16.","DOI":"10.1109\/LICS.2015.16"},{"key":"12_CR49","doi-asserted-by":"publisher","unstructured":"J\u00e9r\u00f4me Leroux and Sylvain Schmitz. \u201cReachability in Vector Addition Systems is Primitive-Recursive in Fixed Dimension\u201d. In: 34th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2019, Vancouver, BC, Canada, June 24-27, 2019. IEEE, 2019, pp. 1\u201313. doi: https:\/\/doi.org\/10.1109\/LICS.2019.8785796.","DOI":"10.1109\/LICS.2019.8785796"},{"key":"12_CR50","doi-asserted-by":"crossref","unstructured":"Ernst W. Mayr. \u201cAn Algorithm for the General Petri Net Reachability Problem\u201d. In: STOC 1981, May 11-13, 1981, Milwaukee, Wisconsin, USA. 1981, pp. 238\u2013246.","DOI":"10.1145\/800076.802477"},{"key":"12_CR51","doi-asserted-by":"crossref","unstructured":"Rohit J Parikh. \u201cOn context-free languages\u201d. In: Journal of the ACM (JACM) 13.4 (1966), pp. 570\u2013581.","DOI":"10.1145\/321356.321364"},{"key":"12_CR52","doi-asserted-by":"publisher","unstructured":"Pawel Parys. \u201cThe Complexity of the Diagonal Problem for Recursion Schemes\u201d. In: 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017, December 11-15, 2017, Kanpur, India. Ed. by Satya V. Lokam and R. Ramanujam. Vol. 93. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2017, 45:1\u201345:14. doi: https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2017.45.","DOI":"10.4230\/LIPIcs.FSTTCS.2017.45"},{"key":"12_CR53","doi-asserted-by":"publisher","unstructured":"Loic Pottier. \u201cMinimal Solutions of Linear Diophantine Systems: Bounds and Algorithms\u201d. In: Rewriting Techniques and Applications, 4th International Conference, RTA-91, Como, Italy, April 10-12, 1991, Proceedings. Ed. by Ronald V. Book. Vol. 488. Lecture Notes in Computer Science. Springer, 1991, pp. 162\u2013173. doi: https:\/\/doi.org\/10.1007\/3-540-53904-2_94.","DOI":"10.1007\/3-540-53904-2_94"},{"key":"12_CR54","doi-asserted-by":"crossref","unstructured":"George S. Sacerdote and Richard L. Tenney. \u201cThe decidability of the reachability problem for vector addition systems (preliminary version)\u201d. In: STOC 1977. ACM. 1977, pp. 61\u201376.","DOI":"10.1145\/800105.803396"},{"key":"12_CR55","doi-asserted-by":"publisher","unstructured":"Kumar Neeraj Verma, Helmut Seidl, and Thomas Schwentick. \u201cOn the Complexity of Equational Horn Clauses\u201d. In: Automated Deduction - CADE-20, 20th International Conference on Automated Deduction, Tallinn, Estonia, July 22-27, 2005, Proceedings. Ed. by Robert Nieuwenhuis. Vol. 3632. Lecture Notes in Computer Science. Springer, 2005, pp. 337\u2013352. doi: https:\/\/doi.org\/10.1007\/11532231_25.","DOI":"10.1007\/11532231_25"},{"key":"12_CR56","doi-asserted-by":"publisher","unstructured":"Georg Zetzsche. \u201cAn Approach to Computing Downward Closures\u201d. In: Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part II. Ed. by Magn\u00fas M. Halld\u00f3rsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann. Vol. 9135. Lecture Notes in Computer Science. Springer, 2015, pp. 440\u2013451. doi: https:\/\/doi.org\/10.1007\/978-3-662-47666-6_35.","DOI":"10.1007\/978-3-662-47666-6_35"},{"key":"12_CR57","unstructured":"Georg Zetzsche. \u201cAn approach to computing downward closures\u201d. In: CoRR abs\/1503.01068 (2015). arXiv: 1503.01068."},{"key":"12_CR58","doi-asserted-by":"publisher","unstructured":"Georg Zetzsche. \u201cThe Complexity of Downward Closure Comparisons\u201d. In: 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy. Ed. by Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi. Vol. 55. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2016, 123:1\u2013123:14. doi: https:\/\/doi.org\/10.4230\/IPIcs.ICALP.2016.123.","DOI":"10.4230\/IPIcs.ICALP.2016.123"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computation Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-30829-1_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,18]],"date-time":"2024-10-18T22:42:13Z","timestamp":1729291333000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-30829-1_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031308284","9783031308291"],"references-count":58,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-30829-1_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"21 April 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FoSSaCS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Foundations of Software Science and Computation Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Paris","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 April 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 April 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fossacs2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/etaps.org\/2023\/fossacs","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"85","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"26","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"31% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.1","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"10","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}