{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:35:45Z","timestamp":1759638945910,"version":"3.40.3"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319948119"},{"type":"electronic","value":"9783319948126"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-94812-6_18","type":"book-chapter","created":{"date-parts":[[2018,6,28]],"date-time":"2018-06-28T22:12:26Z","timestamp":1530223946000},"page":"211-222","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Semilinearity of Families of Languages"],"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":[[2018,6,29]]},"reference":[{"issue":"4","key":"18_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\u2013an extension of context-free grammars. J. ACM 15(4), 647\u2013671 (1968)","journal-title":"J. ACM"},{"issue":"3","key":"18_CR2","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":"18_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/978-3-319-53733-7_21","volume-title":"Language and Automata Theory and Applications","author":"F D\u2019Alessandro","year":"2017","unstructured":"D\u2019Alessandro, F., Ibarra, O.H., McQuillan, I.: On finite-index indexed grammars and their restrictions. In: Drewes, F., Mart\u00edn-Vide, C., Truthe, B. (eds.) LATA 2017. LNCS, vol. 10168, pp. 287\u2013298. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-53733-7_21"},{"key":"18_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/10722167_9","volume-title":"Computer Aided Verification","author":"Z Dang","year":"2000","unstructured":"Dang, Z., Ibarra, O.H., Bultan, T., Kemmerer, R.A., Su, J.: Binary reachability analysis of discrete pushdown timed automata. In: Emerson, E.A., Sistla, A.P. (eds.) CAV 2000. LNCS, vol. 1855, pp. 69\u201384. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/10722167_9"},{"issue":"1\u20132","key":"18_CR5","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0304-3975(84)90023-9","volume":"32","author":"J Duske","year":"1984","unstructured":"Duske, J., Parchmann, R.: Linear indexed languages. Theoret. Comput. Sci. 32(1\u20132), 47\u201360 (1984)","journal-title":"Theoret. Comput. Sci."},{"key":"18_CR6","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":"4","key":"18_CR7","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/S0022-0000(71)80024-7","volume":"5","author":"S Ginsburg","year":"1971","unstructured":"Ginsburg, S., Spanier, E.H.: AFL with the semilinear property. J. Comput. Syst. Sci. 5(4), 365\u2013396 (1971)","journal-title":"J. Comput. Syst. Sci."},{"key":"18_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1007\/978-3-642-31424-7_22","volume-title":"Computer Aided Verification","author":"M Hague","year":"2012","unstructured":"Hague, M., Lin, A.W.: Synchronisation- and reversal-bounded analysis of multithreaded programs with counters. In: Madhusudan, P., Seshia, S.A. (eds.) CAV 2012. LNCS, vol. 7358, pp. 260\u2013276. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-31424-7_22"},{"key":"18_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/978-3-319-45994-3_11","volume-title":"Reachability Problems","author":"M Hague","year":"2016","unstructured":"Hague, M., Lin, A.W.: Decidable models of integer-manipulating programs with recursive parallelism. In: Larsen, K.G., Potapov, I., Srba, J. (eds.) RP 2016. LNCS, vol. 9899, pp. 148\u2013162. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-45994-3_11"},{"key":"18_CR10","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.W.: 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":"18_CR11","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.H., 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."},{"key":"18_CR12","series-title":"Addison-Wesley Series in Computer Science","volume-title":"Introduction to Formal Language Theory","author":"M Harrison","year":"1978","unstructured":"Harrison, M.: Introduction to Formal Language Theory. Addison-Wesley Series in Computer Science. Addison-Wesley Pub. Co., Boston (1978)"},{"key":"18_CR13","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":"18_CR14","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)"},{"issue":"1","key":"18_CR15","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":"18_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/3-540-44618-4_15","volume-title":"CONCUR 2000 \u2014 Concurrency Theory","author":"OH Ibarra","year":"2000","unstructured":"Ibarra, O.H., Bultan, T., Su, J.: Reachability analysis for some models of infinite-state transition systems. In: Palamidessi, C. (ed.) CONCUR 2000. LNCS, vol. 1877, pp. 183\u2013198. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/3-540-44618-4_15"},{"issue":"6","key":"18_CR17","doi-asserted-by":"publisher","first-page":"821","DOI":"10.1142\/S0129054101000898","volume":"12","author":"OH Ibarra","year":"2001","unstructured":"Ibarra, O.H., Bultan, T., Su, J.: On reachability and safety in infinite-state systems. Int. J. Found. Comput. Sci. 12(6), 821\u2013836 (2001)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"1\u20133","key":"18_CR18","doi-asserted-by":"publisher","first-page":"687","DOI":"10.1016\/S0304-3975(02)00545-5","volume":"299","author":"OH Ibarra","year":"2003","unstructured":"Ibarra, O.H., Dang, Z.: Eliminating the storage tape in reachability constructions. Theoret. Comput. Sci. 299(1\u20133), 687\u2013706 (2003)","journal-title":"Theoret. Comput. Sci."},{"key":"18_CR19","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/j.tcs.2016.02.034","volume":"627","author":"OH Ibarra","year":"2016","unstructured":"Ibarra, O.H., McQuillan, I.: The effect of end-markers on counter machines and commutativity. Theoret. Comput. Sci. 627, 71\u201381 (2016)","journal-title":"Theoret. Comput. Sci."},{"key":"18_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/978-3-319-62809-7_17","volume-title":"Developments in Language Theory","author":"OH Ibarra","year":"2017","unstructured":"Ibarra, O.H., McQuillan, I.: Variations of checking stack automata: obtaining unexpected decidability properties. In: Charlier, \u00c9., Leroy, J., Rigo, M. (eds.) DLT 2017. LNCS, vol. 10396, pp. 235\u2013246. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-62809-7_17"},{"issue":"1","key":"18_CR21","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/S0304-3975(01)00268-7","volume":"289","author":"OH Ibarra","year":"2002","unstructured":"Ibarra, O.H., Su, J., Dang, Z., Bultan, T., Kemmerer, R.: Counter machines and verification problems. Theoret. Comput. Sci. 289(1), 165\u2013189 (2002)","journal-title":"Theoret. Comput. Sci."},{"key":"18_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1007\/3-540-44612-5_38","volume-title":"Mathematical Foundations of Computer Science 2000","author":"OH Ibarra","year":"2000","unstructured":"Ibarra, O.H., Su, J., Dang, Z., Bultan, T., Kemmerer, R.: Counter machines: decidable properties and applications to verification problems. In: Nielsen, M., Rovan, B. (eds.) MFCS 2000. LNCS, vol. 1893, pp. 426\u2013435. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/3-540-44612-5_38"},{"issue":"4","key":"18_CR23","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1145\/321356.321364","volume":"13","author":"R Parikh","year":"1966","unstructured":"Parikh, R.: On context-free languages. J. ACM 13(4), 570\u2013581 (1966)","journal-title":"J. ACM"},{"key":"18_CR24","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"},{"key":"18_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1007\/978-3-662-47666-6_35","volume-title":"Automata, Languages, and Programming","author":"G Zetzsche","year":"2015","unstructured":"Zetzsche, G.: An approach to computing downward closures. In: Halld\u00f3rsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9135, pp. 440\u2013451. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-47666-6_35"}],"container-title":["Lecture Notes in Computer Science","Implementation and Application of Automata"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-94812-6_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T15:54:19Z","timestamp":1709826859000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-94812-6_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319948119","9783319948126"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-94812-6_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"29 June 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Implementation and Application of Automata","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Charlottetown, PE","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 July 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 August 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wia2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.smcs.upei.ca\/ciaa2018","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}