{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T22:43:44Z","timestamp":1757630624935,"version":"3.44.0"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,6,14]],"date-time":"2025-06-14T00:00:00Z","timestamp":1749859200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,6,14]],"date-time":"2025-06-14T00:00:00Z","timestamp":1749859200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["2022-05092"],"award-info":[{"award-number":["2022-05092"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Nat Comput"],"published-print":{"date-parts":[[2025,9]]},"DOI":"10.1007\/s11047-025-10032-x","type":"journal-article","created":{"date-parts":[[2025,6,14]],"date-time":"2025-06-14T13:58:47Z","timestamp":1749909527000},"page":"679-691","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On decidability of problems involving insertion operations"],"prefix":"10.1007","volume":"24","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":[[2025,6,14]]},"reference":[{"key":"10032_CR1","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1145\/321479.321488","volume":"15","author":"AV Aho","year":"1968","unstructured":"Aho AV (1968) Indexed grammars\u2014an extension of context-free grammars. J ACM 15:647\u2013671","journal-title":"J ACM"},{"key":"10032_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/978-3-642-20000-7_4","volume-title":"Computation, coorperation, and life: essays dedicated to gheorghe P\u0103un on the occasion of His 60th birthday","author":"P Bottoni","year":"2009","unstructured":"Bottoni P, Gramatovici R, Labella A, Manea F, Mitrana V (2009) Context insertions. In: Coleman J, Kelemenov\u00e1 A (eds) Computation, coorperation, and life: essays dedicated to gheorghe P\u0103un on the occasion of His 60th birthday, vol 6610. Lecture Notes in Computer Science. Springer, Berlin, pp 24\u201334"},{"key":"10032_CR3","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.tcs.2019.04.019","volume":"798","author":"D-J Cho","year":"2019","unstructured":"Cho D-J, Han Y-S, Salomaa K, Smith TJ (2019) Site-directed insertion: language equations and decision problems. Theoret Comput Sci 798:40\u201351","journal-title":"Theoret Comput Sci"},{"issue":"8","key":"10032_CR4","doi-asserted-by":"publisher","first-page":"714","DOI":"10.1016\/j.tcs.2010.11.009","volume":"412","author":"B Cui","year":"2011","unstructured":"Cui B, Kari L, Seki S (2011) Block insertion and deletion on trajectories. Theoret Comput Sci 412(8):714\u2013728","journal-title":"Theoret Comput Sci"},{"key":"10032_CR5","volume-title":"Handbook of formal languages","author":"J Dassow","year":"1997","unstructured":"Dassow J, P\u0103un G, Salomaa A (1997) Grammars with Controlled Derivations. In: Rozenberg G, Salomaa A (eds) Handbook of formal languages, vol 2. Springer, Berlin"},{"key":"10032_CR6","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/s11047-015-9538-x","volume":"16","author":"SK Eneganti","year":"2016","unstructured":"Eneganti SK, Ibarra OH, Kari L, Kopecki S (2016) On the overlap assembly of strings and languages. Nat Comput 16:175\u2013185","journal-title":"Nat Comput"},{"key":"10032_CR7","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/j.ic.2017.01.009","volume":"253","author":"SK Eneganti","year":"2017","unstructured":"Eneganti SK, Ibarra OH, Kari L, Kopecki S (2017) Further remarks on DNA overlap assembly. Inf Comput 253:143\u2013154","journal-title":"Inf Comput"},{"key":"10032_CR8","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1016\/j.ic.2017.09.002","volume":"259","author":"J Eremondi","year":"2018","unstructured":"Eremondi J, Ibarra OH, McQuillan I (2018) On the complexity and decidability of some problems involving shuffle. Inf Comput 259:214\u2013224","journal-title":"Inf Comput"},{"key":"10032_CR9","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/j.jcss.2018.02.003","volume":"104","author":"J Eremondi","year":"2019","unstructured":"Eremondi J, Ibarra OH, McQuillan I (2019) Insertion operations on deterministic reversal-bounded counter machines. J Comput Syst Sci 104:244\u2013257","journal-title":"J Comput Syst Sci"},{"issue":"6","key":"10032_CR10","doi-asserted-by":"publisher","first-page":"620","DOI":"10.1016\/S0019-9958(66)80019-0","volume":"9","author":"S Ginsburg","year":"1966","unstructured":"Ginsburg S, Greibach S (1966) Deterministic context free languages. Inf Control 9(6):620\u2013648","journal-title":"Inf Control"},{"key":"10032_CR11","doi-asserted-by":"crossref","unstructured":"Ginsburg S, Spanier EH (1965) Mappings of languages by two-tape devices. Journal of the ACM, p. 423\u2013434","DOI":"10.1145\/321281.321294"},{"key":"10032_CR12","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 (1978) Remarks on blind and partially blind one-way multicounter machines. Theoret Comput Sci 7:311\u2013324","journal-title":"Theoret Comput Sci"},{"key":"10032_CR13","volume-title":"Introduction to formal language theory","author":"MA Harrison","year":"1978","unstructured":"Harrison MA (1978) Introduction to formal language theory. Addison-Wesley series in computer science. Addison-Wesley Pub. Co., Philippines"},{"key":"10032_CR14","volume-title":"Introduction to automata theory, languages, and computation","author":"JE Hopcroft","year":"1979","unstructured":"Hopcroft JE, Ullman JD (1979) Introduction to automata theory, languages, and computation. Addison-Wesley, Reading, MA"},{"issue":"1","key":"10032_CR15","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1145\/322047.322058","volume":"25","author":"OH Ibarra","year":"1978","unstructured":"Ibarra OH (1978) Reversal-bounded multicounter machines and their decision problems. J ACM 25(1):116\u2013133","journal-title":"J ACM"},{"issue":"8","key":"10032_CR16","doi-asserted-by":"publisher","first-page":"1179","DOI":"10.1142\/S0129054120420095","volume":"31","author":"OH Ibarra","year":"2020","unstructured":"Ibarra OH, McQuillan I (2020) Semilinearity of families of languages. Int J Found Comput Sci 31(8):1179\u20131198","journal-title":"Int J Found Comput Sci"},{"key":"10032_CR17","doi-asserted-by":"publisher","first-page":"105080","DOI":"10.1016\/j.ic.2023.105080","volume":"294","author":"OH Ibarra","year":"2023","unstructured":"Ibarra OH, McQuillan I (2023) On the complexity of decision problems for some classes of machines and applications. Inf Comput 294:105080","journal-title":"Inf Comput"},{"key":"10032_CR18","doi-asserted-by":"publisher","first-page":"114905","DOI":"10.1016\/j.tcs.2024.114905","volume":"1024","author":"OH Ibarra","year":"2025","unstructured":"Ibarra OH, McQuillan I (2025) On decision problems concerning contextual insertions and deletions. Theoret Comput Sci 1024:114905","journal-title":"Theoret Comput Sci"},{"issue":"1","key":"10032_CR19","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1137\/S0097539792240625","volume":"23","author":"OH Ibarra","year":"1995","unstructured":"Ibarra OH, Jiang T, Tran N, Wang H (1995) New decidability results concerning two-way counter machines. SIAM J Comput 23(1):123\u2013137","journal-title":"SIAM J Comput"},{"key":"10032_CR20","unstructured":"Kari L (1991) On insertions and deletions in formal languages. PhD thesis, University of Turku, Finland"},{"issue":"07","key":"10032_CR21","doi-asserted-by":"publisher","first-page":"1655","DOI":"10.1142\/S0129054111008945","volume":"22","author":"L Kari","year":"2011","unstructured":"Kari L, Seki S (2011) Schema for parallel insertion and deletion: revisited. Int J Found Comput Sci 22(07):1655\u20131668","journal-title":"Int J Found Comput Sci"},{"issue":"1","key":"10032_CR22","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1006\/inco.1996.0091","volume":"131","author":"L Kari","year":"1996","unstructured":"Kari L, Thierrin G (1996) Contextual insertions\/deletions and computability. Inf Comput 131(1):47\u201361","journal-title":"Inf Comput"},{"issue":"7","key":"10032_CR23","doi-asserted-by":"publisher","first-page":"1747","DOI":"10.1142\/S0129054111009008","volume":"22","author":"L Kuppusamy","year":"2011","unstructured":"Kuppusamy L, Mahendran A (2011) On the ambiguity of insertion systems. Int J Found Comput Sci 22(7):1747\u20131758","journal-title":"Int J Found Comput Sci"},{"key":"10032_CR24","doi-asserted-by":"crossref","unstructured":"Marcus S (1969) Contextual grammars. In: Proceedings of the 1969 conference on computational linguistics, pp. 1\u201318. Association for computational linguistics, S\u00e5ng-S\u00e4by, Sweden","DOI":"10.3115\/990403.990451"},{"issue":"1","key":"10032_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00163-1","volume":"197","author":"A Mateescu","year":"1998","unstructured":"Mateescu A, Rozenberg G, Salomaa A (1998) Shuffle on trajectories: syntactic constraints. Theoret Comput Sci 197(1):1\u201356","journal-title":"Theoret Comput Sci"},{"issue":"3","key":"10032_CR26","doi-asserted-by":"publisher","first-page":"437","DOI":"10.2307\/1970290","volume":"74","author":"ML Minsky","year":"1961","unstructured":"Minsky ML (1961) Recursive unsolvability of Post\u2019s problem of \u201ctag\u2019\u2019 and other topics in theory of Turing Machines. Ann Math 74(3):437\u2013455","journal-title":"Ann Math"},{"key":"10032_CR27","unstructured":"P\u0103un G, Nguyen XM (1980) On the inner contextual grammars. Rev. Roum. Math. Pures Appl. 25:641\u2013651"}],"container-title":["Natural Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-025-10032-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11047-025-10032-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-025-10032-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T19:19:53Z","timestamp":1757531993000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11047-025-10032-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,14]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,9]]}},"alternative-id":["10032"],"URL":"https:\/\/doi.org\/10.1007\/s11047-025-10032-x","relation":{},"ISSN":["1567-7818","1572-9796"],"issn-type":[{"type":"print","value":"1567-7818"},{"type":"electronic","value":"1572-9796"}],"subject":[],"published":{"date-parts":[[2025,6,14]]},"assertion":[{"value":"29 May 2025","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 June 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}