{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,27]],"date-time":"2026-07-27T20:04:52Z","timestamp":1785182692061,"version":"3.55.0"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032014740","type":"print"},{"value":"9783032014757","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,8,17]],"date-time":"2025-08-17T00:00:00Z","timestamp":1755388800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,8,17]],"date-time":"2025-08-17T00:00:00Z","timestamp":1755388800000},"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":[[2026]]},"DOI":"10.1007\/978-3-032-01475-7_5","type":"book-chapter","created":{"date-parts":[[2025,8,16]],"date-time":"2025-08-16T17:39:15Z","timestamp":1755365955000},"page":"61-76","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Relativized Codes, Finite Decodability, and\u00a0Bounded Languages"],"prefix":"10.1007","author":[{"given":"Oscar H.","family":"Ibarra","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ian","family":"McQuillan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,8,17]]},"reference":[{"key":"5_CR1","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1145\/321479.321488","volume":"15","author":"A Aho","year":"1968","unstructured":"Aho, A.: Indexed grammars \u2013 an extension of context-free grammars. J. ACM 15, 647\u2013671 (1968)","journal-title":"J. ACM"},{"key":"5_CR2","doi-asserted-by":"crossref","unstructured":"Baumann, P., et al.: Unboundedness problems for machines with reversal-bounded counters. In: Lecture Notes in Computer Science. Proceedings of the 26th International Conference on Foundations of Software Science and Computation Structures, FoSSaCS 2023, vol. 13992, pp. 240\u2013264 (2023)","DOI":"10.1007\/978-3-031-30829-1_12"},{"issue":"3","key":"5_CR3","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1142\/S0129054196000191","volume":"7","author":"L Breveglieri","year":"1996","unstructured":"Breveglieri, L., Cherubini, A., Citrini, C., Reghizzi, S.: Multi-push-down languages and grammars. Int. J. Found. Comput. Sci. 7(3), 253\u2013291 (1996)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"5_CR4","doi-asserted-by":"publisher","unstructured":"Handbook of Formal Languages. Springer, Heidelberg (1997). https:\/\/doi.org\/10.1007\/978-3-642-59136-5_9","DOI":"10.1007\/978-3-642-59136-5_9"},{"key":"5_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, Germany (2018)"},{"key":"5_CR6","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2020.104613","volume":"279","author":"F D\u2019Alessandro","year":"2021","unstructured":"D\u2019Alessandro, F., Ibarra, O.H., McQuillan, I.: On finite-index indexed grammars and their restrictions. Inf. Comput. 279, 104613 (2021)","journal-title":"Inf. Comput."},{"key":"5_CR7","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/j.tcs.2011.12.024","volume":"429","author":"M Daley","year":"2012","unstructured":"Daley, M., J\u00fcrgensen, H., Kari, L., Mahalingam, K.: Relativized codes. Theoret. Comput. Sci. 429, 54\u201364 (2012)","journal-title":"Theoret. Comput. Sci."},{"key":"5_CR8","doi-asserted-by":"crossref","unstructured":"Dassow, J., P\u0103un, G., Salomaa, A.: Handbook of Formal Languages, vol.\u00a02, chap. Grammars with Controlled Derivations. Springer-Verlag, Berlin (1997)","DOI":"10.1007\/978-3-662-07675-0_3"},{"key":"5_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1998.2715","volume":"145","author":"F Drewes","year":"1998","unstructured":"Drewes, F., Engelfriet, J.: Decidability of the finiteness of ranges of tree transductions. Inf. Comput. 145, 1\u201350 (1998)","journal-title":"Inf. Comput."},{"key":"5_CR10","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, 21\u201375 (1991)","journal-title":"Inf. Comput."},{"key":"5_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1007\/978-3-319-21500-6_18","volume-title":"Developments in Language Theory","author":"J Eremondi","year":"2015","unstructured":"Eremondi, J., Ibarra, O.H., McQuillan, I.: On the density of context-free and counter languages. In: Potapov, I. (ed.) DLT 2015. LNCS, vol. 9168, pp. 228\u2013239. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21500-6_18"},{"key":"5_CR12","doi-asserted-by":"crossref","unstructured":"Fernau, H., Reinhardt, K., Staiger, L.: Decidability of code properties. RAIRO \u2014 Theor. Inform. Appl. 41, pp. 243\u2013259 (2007)","DOI":"10.1051\/ita:2007019"},{"key":"5_CR13","volume-title":"Algebraic and Automata-Theoretic Properties of Formal Languages","author":"S Ginsburg","year":"1975","unstructured":"Ginsburg, S.: Algebraic and Automata-Theoretic Properties of Formal Languages. North-Holland Publishing Company, Amsterdam (1975)"},{"issue":"2","key":"5_CR14","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":"5_CR15","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, NY, USA (1966)"},{"issue":"2","key":"5_CR16","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":"5_CR17","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/S0019-9958(63)90149-9","volume":"6","author":"SA Greibach","year":"1963","unstructured":"Greibach, S.A.: Minimal linear grammars. Inf. Control 6, 119\u2013125 (1963)","journal-title":"Inf. Control"},{"key":"5_CR18","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":"5_CR19","doi-asserted-by":"publisher","first-page":"719","DOI":"10.1007\/BF01178731","volume":"31","author":"D Hauschildt","year":"1994","unstructured":"Hauschildt, D., Jantzen, M.: Petri net algorithms in the theory of matrix grammars. Acta Informatica 31, 719\u2013728 (1994)","journal-title":"Acta Informatica"},{"key":"5_CR20","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1007\/3-540-45061-0_40","volume-title":"Automata, Languages and Programming: 30th International Colloquium, ICALP 2003 Eindhoven, The Netherlands, June 30 - July 4, 2003 Proceedings","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.) Automata, Languages and Programming: 30th International Colloquium, ICALP 2003 Eindhoven, The Netherlands, June 30 - July 4, 2003 Proceedings, pp. 490\u2013501. Springer, Berlin Heidelberg (2003)"},{"key":"5_CR21","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, MA (1979)"},{"issue":"1","key":"5_CR22","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"},{"issue":"8","key":"5_CR23","doi-asserted-by":"publisher","first-page":"1179","DOI":"10.1142\/S0129054120420095","volume":"31","author":"OH Ibarra","year":"2020","unstructured":"Ibarra, O.H., McQuillan, I.: Semilinearity of families of languages. Int. J. Found. Comput. Sci. 31(8), 1179\u20131198 (2020)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"5_CR24","doi-asserted-by":"crossref","unstructured":"Ibarra, O.H., McQuillan, I.: Techniques for showing the decidability of the boundedness problem of language acceptors. In: Lecture Notes in Computer Science. Proceedings of the 28th International Conference on Developments in Language Theory, DLT 2024, vol. 14791, pp. 156\u2013172 (2024)","DOI":"10.1007\/978-3-031-66159-4_12"},{"key":"5_CR25","doi-asserted-by":"publisher","unstructured":"Handbook of Formal Languages. Lecture Notes in Computer Science, Springer, Heidelberg (1997). https:\/\/doi.org\/10.1007\/978-3-642-59136-5_9","DOI":"10.1007\/978-3-642-59136-5_9"},{"issue":"05","key":"5_CR26","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1142\/S0129054121410057","volume":"32","author":"SK Ko","year":"2021","unstructured":"Ko, S.K., Han, Y.S., Salomaa, K.: Generalizations of code languages with marginal errors. Int. J. Found. Comput. Sci. 32(05), 509\u2013529 (2021)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"5_CR27","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/S0019-9958(78)90050-5","volume":"38","author":"G Rozenberg","year":"1978","unstructured":"Rozenberg, G., Vermeir, D.: On ET0L systems of finite index. Inf. Control 38, 103\u2013133 (1978)","journal-title":"Inf. Control"}],"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-032-01475-7_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,27]],"date-time":"2026-07-27T19:28:16Z","timestamp":1785180496000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-01475-7_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,17]]},"ISBN":["9783032014740","9783032014757"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-01475-7_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,8,17]]},"assertion":[{"value":"17 August 2025","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":"Seoul","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Korea (Republic of)","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 August 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 August 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"dlt2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/cida.uos.ac.kr\/dlt2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}