{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T21:32:03Z","timestamp":1757453523676,"version":"3.40.3"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031661587"},{"type":"electronic","value":"9783031661594"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-3-031-66159-4_12","type":"book-chapter","created":{"date-parts":[[2024,7,26]],"date-time":"2024-07-26T09:01:34Z","timestamp":1721984494000},"page":"156-172","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Techniques for\u00a0Showing the\u00a0Decidability of\u00a0the\u00a0Boundedness Problem of\u00a0Language Acceptors"],"prefix":"10.1007","author":[{"given":"Oscar H.","family":"Ibarra","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ian","family":"McQuillan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,7,27]]},"reference":[{"key":"12_CR1","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1145\/321479.321488","volume":"15","author":"AV Aho","year":"1968","unstructured":"Aho, A.V.: Indexed grammars\u2014an extension of context-free grammars. J. ACM 15, 647\u2013671 (1968)","journal-title":"J. ACM"},{"issue":"3","key":"12_CR2","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/S0022-0000(74)80027-9","volume":"8","author":"BS Baker","year":"1974","unstructured":"Baker, B.S., Book, R.V.: Reversal-bounded multipushdown machines. J. Comput. Syst. Sci. 8(3), 315\u2013332 (1974)","journal-title":"J. Comput. Syst. Sci."},{"key":"12_CR3","doi-asserted-by":"crossref","unstructured":"Baumann, P., et al.: Unboundedness problems for machines with reversal-bounded counters. In: 25th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS) (2023)","DOI":"10.1007\/978-3-031-30829-1_12"},{"issue":"08","key":"12_CR4","doi-asserted-by":"publisher","first-page":"1691","DOI":"10.1142\/S0129054112400709","volume":"23","author":"M Cadilhac","year":"2012","unstructured":"Cadilhac, M., Finkel, A., McKenzie, P.: Bounded Parikh automata. Int. J. Found. Comput. Sci. 23(08), 1691\u20131709 (2012)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"12_CR5","unstructured":"Czerwinski, W., Hofman, P., Zetzsche, G.: Unboundedness problems for languages of vector addition systems. In: Chatzigiannakis, I., Kaklamanis, C., Marx, D., Sannella, D. (eds.) 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), vol. 107, p. 119. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl (2018)"},{"issue":"2","key":"12_CR6","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1016\/0890-5401(89)90015-1","volume":"80","author":"J Engelfriet","year":"1989","unstructured":"Engelfriet, J.: The power of two-way deterministic checking stack automata. Inf. Comput. 80(2), 114\u2013120 (1989)","journal-title":"Inf. Comput."},{"issue":"1","key":"12_CR7","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/0890-5401(91)90015-T","volume":"95","author":"J Engelfriet","year":"1991","unstructured":"Engelfriet, J.: Iterated stack automata and complexity classes. Inf. Comput. 95(1), 21\u201375 (1991)","journal-title":"Inf. Comput."},{"issue":"6","key":"12_CR8","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0020-0190(76)90086-7","volume":"4","author":"J Engelfriet","year":"1976","unstructured":"Engelfriet, J., Skyum, S.: Copying theorems. Inf. Process. Lett. 4(6), 157\u2013161 (1976)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"12_CR9","first-page":"333","volume":"113","author":"S Ginsburg","year":"1964","unstructured":"Ginsburg, S., Spanier, E.: Bounded Algol-like languages. Trans. Am. Math. Soc. 113(2), 333\u2013368 (1964)","journal-title":"Trans. Am. Math. Soc."},{"key":"12_CR10","volume-title":"The Mathematical Theory of Context-Free Languages","author":"S Ginsburg","year":"1966","unstructured":"Ginsburg, S.: The Mathematical Theory of Context-Free Languages. McGraw-Hill Inc., New York (1966)"},{"key":"12_CR11","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/0304-3975(78)90020-8","volume":"7","author":"S Greibach","year":"1978","unstructured":"Greibach, S.: Remarks on blind and partially blind one-way multicounter machines. Theoret. Comput. Sci. 7, 311\u2013324 (1978)","journal-title":"Theoret. Comput. Sci."},{"key":"12_CR12","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1090\/S0002-9939-1967-0209086-1","volume":"18","author":"S Greibach","year":"1967","unstructured":"Greibach, S.: A note on pushdown store automata and regular systems. Proc. Am. Math. Soc. 18, 263\u2013268 (1967)","journal-title":"Proc. Am. Math. Soc."},{"issue":"2","key":"12_CR13","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1016\/S0022-0000(69)80012-7","volume":"3","author":"S Greibach","year":"1969","unstructured":"Greibach, S.: Checking automata and one-way stack languages. J. Comput. Syst. Sci. 3(2), 196\u2013217 (1969)","journal-title":"J. Comput. Syst. Sci."},{"key":"12_CR14","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/0304-3975(78)90035-X","volume":"6","author":"SA Greibach","year":"1978","unstructured":"Greibach, S.A.: One way finite visit automata. Theoret. Comput. Sci. 6, 175\u2013221 (1978)","journal-title":"Theoret. Comput. Sci."},{"key":"12_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"743","DOI":"10.1007\/978-3-642-22110-1_60","volume-title":"Computer Aided Verification","author":"M Hague","year":"2011","unstructured":"Hague, M., Lin, A.: Model checking recursive programs with numeric data types. In: Gopalakrishnan, G., Qadeer, S. (eds.) CAV 2011. LNCS, vol. 6806, pp. 743\u2013759. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-22110-1_60"},{"issue":"2","key":"12_CR16","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1006\/jcss.2002.1836","volume":"65","author":"T Harju","year":"2002","unstructured":"Harju, T., Ibarra, O., Karhum\u00e4ki, J., Salomaa, A.: Some decision problems concerning semilinearity and commutation. J. Comput. Syst. Sci. 65(2), 278\u2013294 (2002)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"12_CR17","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1016\/S0019-9958(68)90901-7","volume":"13","author":"MA Harrison","year":"1968","unstructured":"Harrison, M.A., Ibarra, O.H.: Multi-tape and multi-head pushdown automata. Inf. Control 13(5), 433\u2013470 (1968)","journal-title":"Inf. Control"},{"key":"12_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/3-540-45007-6_29","volume-title":"Developments in Language Theory","author":"M Holzer","year":"2003","unstructured":"Holzer, M., Kutrib, M.: Flip-pushdown automata: nondeterminism is better than determinism. In: \u00c9sik, Z., F\u00fcl\u00f6p, Z. (eds.) DLT 2003. LNCS, vol. 2710, pp. 361\u2013372. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/3-540-45007-6_29"},{"key":"12_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1007\/3-540-45061-0_40","volume-title":"Automata, Languages and Programming","author":"M Holzer","year":"2003","unstructured":"Holzer, M., Kutrib, M.: Flip-pushdown automata: k + 1 pushdown reversals are better than k. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 490\u2013501. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/3-540-45061-0_40"},{"key":"12_CR20","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"JE Hopcroft","year":"1979","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading (1979)"},{"key":"12_CR21","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/BF01746517","volume":"3","author":"JE Hopcroft","year":"1969","unstructured":"Hopcroft, J.E.: On the equivalence and containment problems for context-free languages. Math. Syst. 3, 119\u2013124 (1969)","journal-title":"Math. Syst."},{"key":"12_CR22","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1016\/j.tcs.2018.05.036","volume":"745","author":"O Ibarra","year":"2018","unstructured":"Ibarra, O., McQuillan, I.: On store languages of languages acceptors. Theoret. Comput. Sci. 745, 114\u2013132 (2018)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"12_CR23","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1016\/S0019-9958(70)80034-1","volume":"17","author":"OH Ibarra","year":"1970","unstructured":"Ibarra, O.H.: Simple matrix languages. Inf. Control 17(4), 359\u2013394 (1970)","journal-title":"Inf. Control"},{"issue":"1","key":"12_CR24","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1145\/322047.322058","volume":"25","author":"OH Ibarra","year":"1978","unstructured":"Ibarra, O.H.: Reversal-bounded multicounter machines and their decision problems. J. ACM 25(1), 116\u2013133 (1978)","journal-title":"J. ACM"},{"key":"12_CR25","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1016\/j.tcs.2018.06.035","volume":"746","author":"OH Ibarra","year":"2018","unstructured":"Ibarra, O.H.: Grammatical characterizations of NPDAs and VPDAs with counters. Theoret. Comput. Sci. 746, 136\u2013150 (2018)","journal-title":"Theoret. Comput. Sci."},{"key":"12_CR26","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1016\/j.ic.2019.03.003","volume":"267","author":"OH Ibarra","year":"2019","unstructured":"Ibarra, O.H., McQuillan, I.: On store languages and applications. Inf. Comput. 267, 28\u201348 (2019)","journal-title":"Inf. Comput."},{"key":"12_CR27","doi-asserted-by":"crossref","unstructured":"Ibarra, O.H., McQuillan, I.: Techniques for showing the decidability of the boundedness problem of language acceptors (2024). https:\/\/arxiv.org\/abs\/2405.08988","DOI":"10.1007\/978-3-031-66159-4_12"},{"issue":"3","key":"12_CR28","doi-asserted-by":"publisher","first-page":"437","DOI":"10.2307\/1970290","volume":"74","author":"ML Minsky","year":"1961","unstructured":"Minsky, M.L.: Recursive unsolvability of Post\u2019s problem of \u201ctag\u2019\u2019 and other topics in theory of Turing Machines. Ann. Math. 74(3), 437\u2013455 (1961)","journal-title":"Ann. Math."},{"issue":"3","key":"12_CR29","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1080\/0020716022000005564","volume":"80","author":"E Moriya","year":"2003","unstructured":"Moriya, E., Tada, T.: On the space complexity of turn bounded pushdown automata. Int. J. Comput. Math. 80(3), 295\u2013304 (2003)","journal-title":"Int. J. Comput. Math."},{"issue":"1","key":"12_CR30","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1016\/0890-5401(87)90012-5","volume":"74","author":"B Rozoy","year":"1987","unstructured":"Rozoy, B.: The Dyck language $${D^{\\prime }}_1^*$$ is not generated by any matrix grammar of finite index. Inf. Comput. 74(1), 64\u201389 (1987)","journal-title":"Inf. Comput."}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-66159-4_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,19]],"date-time":"2024-10-19T08:03:31Z","timestamp":1729325011000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-66159-4_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031661587","9783031661594"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-66159-4_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"27 July 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"DLT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Developments in Language Theory","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"G\u00f6ttingen","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 August 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 August 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"dlt2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}