{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:25:32Z","timestamp":1740108332251,"version":"3.37.3"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,3,24]],"date-time":"2022-03-24T00:00:00Z","timestamp":1648080000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,3,24]],"date-time":"2022-03-24T00:00:00Z","timestamp":1648080000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"name":"JSPS KAKENHI","award":["JP16K16008"],"award-info":[{"award-number":["JP16K16008"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2022,8]]},"DOI":"10.1007\/s00236-022-00418-0","type":"journal-article","created":{"date-parts":[[2022,3,25]],"date-time":"2022-03-25T00:03:16Z","timestamp":1648166596000},"page":"409-426","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["$$\\mathcal {L}$$-reduction computation revisited"],"prefix":"10.1007","volume":"59","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8240-4089","authenticated-orcid":false,"given":"Kaoru","family":"Fujioka","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fumiya","family":"Okubo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takashi","family":"Yokomori","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,3,24]]},"reference":[{"key":"418_CR1","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/0304-3975(82)90036-6","volume":"19","author":"RV Book","year":"1982","unstructured":"Book, R.V., Jantzen, M., Wrathall, C.: Monadic Thue systems. Theor. Comput. Sci. 19, 213\u2013251 (1982)","journal-title":"Theor. Comput. Sci."},{"key":"418_CR2","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1112\/plms\/s3-58.1.74","volume":"58","author":"Ch Frougny","year":"1989","unstructured":"Frougny, Ch., Sakarovitch, J., Schupp, P.: Finiteness conditions on subgroups and formal language theory. Proc. Lond. Math. Soc. 58, 74\u201388 (1989)","journal-title":"Proc. Lond. Math. Soc."},{"key":"418_CR3","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1016\/j.ic.2010.11.011","volume":"209","author":"K Fujioka","year":"2011","unstructured":"Fujioka, K.: Morphic characterizations of languages in Chomsky hierarchy with insertion and locality. Inf. Comput. 209, 397\u2013408 (2011)","journal-title":"Inf. Comput."},{"issue":"10","key":"418_CR4","doi-asserted-by":"publisher","first-page":"1945","DOI":"10.1587\/transinf.E94.D.1945","volume":"94","author":"K Fujioka","year":"2011","unstructured":"Fujioka, K., Katsuno, H.: On the generative power of cancel minimal linear grammars with single nonterminal symbol except the start symbol. IEICE Trans. Inf. Syst. 94(10), 1945\u20131954 (2011)","journal-title":"IEICE Trans. Inf. Syst."},{"key":"418_CR5","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1051\/ita\/1991250504731","volume":"25","author":"V Geffert","year":"1991","unstructured":"Geffert, V.: Normal forms for phrase-structure grammars. RAIRO Theoret. Inf. Appl. 25, 473\u2013496 (1991)","journal-title":"RAIRO Theoret. Inf. Appl."},{"key":"418_CR6","unstructured":"Harrison, M.A.: Introduction to Formal Language Theory, Addison Wesley, Reading, Mass., (1978)"},{"issue":"2","key":"418_CR7","first-page":"161","volume":"79","author":"S Hirose","year":"1996","unstructured":"Hirose, S., Okawa, S.: Dyck reduction of minimal linear languages yield the full class of recursively enumerable languages. IEICE Trans. Inf. Syst. 79(2), 161\u2013164 (1996)","journal-title":"IEICE Trans. Inf. Syst."},{"issue":"3","key":"418_CR8","first-page":"390","volume":"80","author":"S Hirose","year":"1996","unstructured":"Hirose, S., Okawa, S., Kimura, H.: Homomorphic characterizations are more powerful than Dyck reductions. IEICE Trans. Inf. Syst. 80(3), 390\u2013392 (1996)","journal-title":"IEICE Trans. Inf. Syst."},{"key":"418_CR9","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/0304-3975(86)90119-2","volume":"44","author":"S Hirose","year":"1986","unstructured":"Hirose, S., Okawa, S., Yoneda, M.: On the impossibility of the homomorphic characterization of context-sensitive languages. Theor. Comput. Sci. 44, 225\u2013228 (1986)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"418_CR10","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/S0304-3975(99)00277-7","volume":"245","author":"M Ito","year":"2000","unstructured":"Ito, M., Kari, L., Thierrin, G.: Shuffle and scattered deletion closure of languages. Theor. Comput. Sci. 245(1), 115\u2013133 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"418_CR11","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/978-3-642-72822-8_17","volume-title":"Concurrency and Nets","author":"M Jantzen","year":"1987","unstructured":"Jantzen, M., Petersen, H.: Petri net languages and one-sided Dyck$$_1$$-reductions of context-free sets. In: Voss, K., Genrich, H., Rozenberg, G. (eds.) Concurrency and Nets, pp. 245\u2013252. Springer, Berlin (1987)"},{"key":"418_CR12","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0304-3975(94)90104-X","volume":"127","author":"M Jantzen","year":"1994","unstructured":"Jantzen, M., Petersen, H.: Cancellation in context-free languages: enrichment by reduction. Theor. Comput. Sci. 127, 149\u2013170 (1994)","journal-title":"Theor. Comput. Sci."},{"key":"418_CR13","first-page":"3","volume":"9","author":"M Jantzen","year":"1990","unstructured":"Jantzen, M., Kudlek, M., Lange, K.-J., Petersen, H.: Dyck$$_1$$-reductions of context-free languages. Comput. Artif. Intell. 9, 3\u201318 (1990)","journal-title":"Comput. Artif. Intell."},{"key":"418_CR14","unstructured":"Kari, L.: On insertion and deletion in formal languages, PhD, (1991)"},{"issue":"2","key":"418_CR15","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1051\/ita\/1995290201291","volume":"29","author":"L Kari","year":"1995","unstructured":"Kari, L., Mateescu, A., Paun, G., Salomaa, A.: On parallel deletions applied to a word. RAIRO Theor. Inform. Appl. Inform. Th\u00e9or. Appl. 29(2), 129\u2013144 (1995)","journal-title":"RAIRO Theor. Inform. Appl. Inform. Th\u00e9or. Appl."},{"key":"418_CR16","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1016\/j.tcs.2008.01.037","volume":"396","author":"L Kari","year":"2008","unstructured":"Kari, L., Sosik, P.: On the weight of universal insertion grammars. Theor. Comput. Sci. 396, 264\u2013270 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"418_CR17","unstructured":"Kimura, T.: Formal description of communication behavior, In: Proc. Johns Hopkins Conf. on Information Sciences and Systems , 286\u2013291 (1979)"},{"key":"418_CR18","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/BF01237236","volume":"28","author":"M Latteux","year":"1990","unstructured":"Latteux, M., Turakainen, P.: On characterizations of recursively enumerable languages. Acta Inform. 28, 179\u2013186 (1990)","journal-title":"Acta Inform."},{"key":"418_CR19","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1016\/j.tcs.2004.06.031","volume":"330","author":"M Margenstern","year":"2005","unstructured":"Margenstern, M., P\u0103un, Gh., Rogozhin, Y., Verlan, S.: Context-free insertion-deletion systems. Theor. Comput. Sci. 330, 339\u2013348 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"418_CR20","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1142\/S012905411100799X","volume":"22","author":"F Okubo","year":"2011","unstructured":"Okubo, F., Yokomori, T.: Morphic characterizations of language families in terms of insertion systems and star languages. Intern. J. Found. Comput. Sci. 22, 247\u2013260 (2011)","journal-title":"Intern. J. Found. Comput. Sci."},{"key":"418_CR21","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1016\/j.tcs.2020.11.029","volume":"862","author":"F Okubo","year":"2021","unstructured":"Okubo, F., Yokomori, T.: On the computing powers of $$\\cal{L}$$-reductions of insertion languages. Theor. Comput. Sci. 862, 224\u2013235 (2021)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"418_CR22","first-page":"1424","volume":"44","author":"K Onodera","year":"2003","unstructured":"Onodera, K.: A note on homomorphic representation of recursively enumerable languages with insertion grammars. IPSJ J. 44(5), 1424\u20131427 (2003)","journal-title":"IPSJ J."},{"key":"418_CR23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03563-4","volume-title":"DNA Computing: New Computing Paradigms","author":"Gh P\u0103un","year":"1998","unstructured":"P\u0103un, Gh., Rozenberg, G., Salomaa, A.: DNA Computing: New Computing Paradigms. Springer-Verlag, Berlin (1998)"},{"key":"418_CR24","doi-asserted-by":"crossref","unstructured":"P\u0103un, Gh., P$$\\acute{{\\rm e}}$$rez-Jim$$\\acute{{\\rm e}}$$nez, M.J., Yokomori, T.: Representations and characterizations of languages in Chomsky hierarchy by means of insertion-deletion systems, Intern J. Found. Comput. Sci. 19(4), 859\u2013871 (2008)","DOI":"10.1142\/S0129054108006005"},{"issue":"4","key":"418_CR25","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1016\/S0019-9958(74)91049-3","volume":"25","author":"M Penttonen","year":"1974","unstructured":"Penttonen, M.: One-sided and two-sided context in formal grammars. Inf. Control 25(4), 371\u2013392 (1974)","journal-title":"Inf. Control"},{"volume-title":"Handbook of Formal Languages","year":"1997","key":"418_CR26","unstructured":"Rozenberg, G., Salomaa, A. (eds.): Handbook of Formal Languages. Springer-Verlag, Berlin (1997)"},{"key":"418_CR27","volume-title":"Formal Languages","author":"A Salomaa","year":"1973","unstructured":"Salomaa, A.: Formal Languages. Academic Press, Cambridge (1973)"},{"key":"418_CR28","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/S0019-9958(75)90066-2","volume":"27","author":"WJ Savitch","year":"1975","unstructured":"Savitch, W.J.: Some characterizations of Lindenmayer systems in terms of Chomsky-type grammars and stack machines. Inf. Control 27, 37\u201360 (1975)","journal-title":"Inf. Control"},{"key":"418_CR29","doi-asserted-by":"crossref","unstructured":"Savitch, W.J.: Parantheses grammars and Lindenmayer systems, In: Rozenberg, G.,Salomaa, A. (eds), The Book of L, Spriger-Verlag , 403-411 (1986)","DOI":"10.1007\/978-3-642-95486-3_34"},{"issue":"2","key":"418_CR30","first-page":"210","volume":"18","author":"S Verlan","year":"2010","unstructured":"Verlan, S.: Recent developments on insertion-deletion systems. Comput. Sci. J. Moldova 18(2), 210\u2013245 (2010)","journal-title":"Comput. Sci. J. Moldova"},{"key":"418_CR31","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/j.tcs.2020.09.002","volume":"843","author":"S Verlan","year":"2020","unstructured":"Verlan, S., Fernau, H., Kuppusamy, L.: Universal insertion grammars of size two. Theor. Comput. Sci. 843, 153\u2013163 (2020)","journal-title":"Theor. Comput. Sci."}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-022-00418-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-022-00418-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-022-00418-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,27]],"date-time":"2022-08-27T09:08:23Z","timestamp":1661591303000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-022-00418-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,24]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["418"],"URL":"https:\/\/doi.org\/10.1007\/s00236-022-00418-0","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"type":"print","value":"0001-5903"},{"type":"electronic","value":"1432-0525"}],"subject":[],"published":{"date-parts":[[2022,3,24]]},"assertion":[{"value":"1 September 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 February 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 March 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}