{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,2]],"date-time":"2024-08-02T19:52:50Z","timestamp":1722628370312},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,7,18]],"date-time":"2021-07-18T00:00:00Z","timestamp":1626566400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,7,18]],"date-time":"2021-07-18T00:00:00Z","timestamp":1626566400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Nat Comput"],"published-print":{"date-parts":[[2021,12]]},"DOI":"10.1007\/s11047-021-09861-3","type":"journal-article","created":{"date-parts":[[2021,7,18]],"date-time":"2021-07-18T08:03:15Z","timestamp":1626595395000},"page":"703-712","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Single semi-contextual insertion-deletion systems"],"prefix":"10.1007","volume":"20","author":[{"given":"Sergiu","family":"Ivanov","sequence":"first","affiliation":[]},{"given":"Sergey","family":"Verlan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,7,18]]},"reference":[{"issue":"1","key":"9861_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/s41467-018-04252-2","volume":"9","author":"M Adli","year":"2018","unstructured":"Adli M (2018) The CRISPR tool kit for genome editing and beyond. Nat Commun 9(1):1\u201313","journal-title":"Nat Commun"},{"issue":"1\u20132","key":"9861_CR2","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1016\/j.tcs.2010.08.025","volume":"412","author":"A Alhazov","year":"2011","unstructured":"Alhazov A, Krassovitskiy A, Rogozhin Y, Verlan S (2011) P systems with minimal insertion and deletion. Theor Comput Sci 412(1\u20132):136\u2013144","journal-title":"Theor Comput Sci"},{"key":"9861_CR3","unstructured":"Benne R (ed) (1993) RNA editing: the alteration of protein coding sequences of rna. series in molecular biology. Ellis Horwood, Chichester, UK"},{"issue":"2","key":"9861_CR4","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/j.tcs.2007.07.030","volume":"387","author":"F Biegler","year":"2007","unstructured":"Biegler F, Burrell MJ, Daley M (2007) Regulated RNA rewriting: modelling RNA editing with guided insertion. Theor Comput Sci 387(2):103\u2013112","journal-title":"Theor Comput Sci"},{"key":"9861_CR5","doi-asserted-by":"publisher","unstructured":"Castellanos J, Mart\u00edn-Vide C, Mitrana V, Sempere JM (2001) Solving NP-complete problems with networks of evolutionary processors. In: \u00a0Mira J, Prieto A (eds.) Connectionist Models of Neurons, Learning Processes and Artificial Intelligence, 6th International Work-Conference on Artificial and Natural Neural Networks, IWANN 2001 Granada, Spain, June 13-15, 2001, Proceedings, Part I, Lecture Notes in Computer Science, vol. 2084, pp. 621\u2013628. Springer. https:\/\/doi.org\/10.1007\/3-540-45720-8_74","DOI":"10.1007\/3-540-45720-8_74"},{"key":"9861_CR6","doi-asserted-by":"publisher","unstructured":"Fernau H, Kuppusamy L, Raman I (2016) Generative power of matrix insertion-deletion systems with context-free insertion or deletion. In: Amos M, \u00a0Condon A (eds.) Unconventional Computation and Natural Computation - 15th International Conference, UCNC 2016, Manchester, UK, July 11-15, 2016, Proceedings, Lecture Notes in Computer Science, vol. 9726, pp. 35\u201348. Springer. https:\/\/doi.org\/10.1007\/978-3-319-41312-9_4","DOI":"10.1007\/978-3-319-41312-9_4"},{"key":"9861_CR7","doi-asserted-by":"publisher","unstructured":"Fernau H, Kuppusamy L, Raman I (2018) Computational completeness of simple semi-conditional insertion-deletion systems. In: Stepney S, Verlan S (eds.) Unconventional Computation and Natural Computation - 17th International Conference, UCNC 2018, Fontainebleau, France, June 25-29, 2018, Proceedings, Lecture Notes in Computer Science, vol. 10867, pp. 86\u2013100. Springer. https:\/\/doi.org\/10.1007\/978-3-319-92435-9_7","DOI":"10.1007\/978-3-319-92435-9_7"},{"issue":"2","key":"9861_CR8","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/s11047-017-9656-8","volume":"17","author":"H Fernau","year":"2018","unstructured":"Fernau H, Kuppusamy L, Raman I (2018) Investigations on the power of matrix insertion-deletion systems with small sizes. Nat Comput 17(2):249\u2013269. https:\/\/doi.org\/10.1007\/s11047-017-9656-8","journal-title":"Nat Comput"},{"issue":"3","key":"9861_CR9","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1007\/s11047-019-09742-w","volume":"18","author":"H Fernau","year":"2019","unstructured":"Fernau H, Kuppusamy L, Raman I (2019) Computational completeness of simple semi-conditional insertion-deletion systems of degree (2, 1). Nat Comput 18(3):563\u2013577. https:\/\/doi.org\/10.1007\/s11047-019-09742-w","journal-title":"Nat Comput"},{"key":"9861_CR10","doi-asserted-by":"crossref","unstructured":"Fernau H, Kuppusamy L, Raman I (2020) On the power of generalized forbidding insertion-deletion systems. In: Descriptional Complexity of Formal Systems (DCFS 2020)","DOI":"10.1007\/978-3-030-62536-8_5"},{"key":"9861_CR11","doi-asserted-by":"publisher","unstructured":"Fernau H, Kuppusamy L, Verlan S (2017) Universal matrix insertion grammars with small size. In: Patitz MJ,  Stannett M (eds.) Unconventional Computation and Natural Computation - 16th International Conference, UCNC 2017, Fayetteville, AR, USA, June 5-9, 2017, Proceedings, Lecture Notes in Computer Science. 10240: 182\u2013193. Springer. https:\/\/doi.org\/10.1007\/978-3-319-58187-3_14","DOI":"10.1007\/978-3-319-58187-3_14"},{"key":"9861_CR12","doi-asserted-by":"crossref","unstructured":"Freund R, Kogler M, Rogozhin Y, Verlan S (2010) Graph-controlled insertion-deletion systems. In: McQuillan I, Pighizzini G (eds.) Proceedings Twelfth Annual Workshop on Descriptional Complexity of Formal Systems, Electronic Proceedings in Theoretical Computer Science, 31: pp. 88\u201398","DOI":"10.4204\/EPTCS.31.11"},{"key":"9861_CR13","unstructured":"Galiukschov B (1981) Semicontextual grammars. Matem. Logica i Matem. Lingvistika , 38\u201350. Tallin University, (in Russian)"},{"issue":"1","key":"9861_CR14","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1142\/S0129054119400045","volume":"30","author":"Z Gazdag","year":"2019","unstructured":"Gazdag Z, Tichler K, Csuhaj-Varj\u00fa E (2019) A pumping lemma for permitting semi-conditional languages. Int J Found Comput Sci 30(1):73\u201392. https:\/\/doi.org\/10.1142\/S0129054119400045","journal-title":"Int J Found Comput Sci"},{"issue":"1","key":"9861_CR15","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0020-0255(83)90023-3","volume":"31","author":"D Haussler","year":"1983","unstructured":"Haussler D (1983) Insertion languages. Inf Sci 31(1):77\u201389. https:\/\/doi.org\/10.1016\/0020-0255(83)90023-3","journal-title":"Inf Sci"},{"key":"9861_CR16","doi-asserted-by":"crossref","unstructured":"Ivanov S, Verlan S (2013) About one-sided one-symbol insertion-deletion P systems. In: \u00a0Alhazov A, Cojocaru S, \u00a0Gheorghe M, Rogozhin Y, \u00a0Rozenberg G, \u00a0Salomaa A (eds.) Membrane Computing - 14th International Conference, CMC 2013, Chi\u015fin\u0103u, Republic of Moldova, August 20-23, 2013, Revised Selected Papers, Lecture Notes in Computer Science, vol. 8340, pp. 225\u2013237. Springer","DOI":"10.1007\/978-3-642-54239-8_16"},{"issue":"1\u20132","key":"9861_CR17","doi-asserted-by":"publisher","first-page":"127","DOI":"10.3233\/FI-2015-1203","volume":"138","author":"S Ivanov","year":"2015","unstructured":"Ivanov S, Verlan S (2015) Random context and semi-conditional insertion-deletion systems. Fundam Inf 138(1\u20132):127\u2013144. https:\/\/doi.org\/10.3233\/FI-2015-1203","journal-title":"Fundam Inf"},{"issue":"1\u20132","key":"9861_CR18","doi-asserted-by":"publisher","first-page":"163","DOI":"10.3233\/FI-2017-1580","volume":"155","author":"S Ivanov","year":"2017","unstructured":"Ivanov S, Verlan S (2017) Universality and computational completeness of controlled leftist insertion-deletion systems. Fundam Inform 155(1\u20132):163\u2013185. https:\/\/doi.org\/10.3233\/FI-2017-1580","journal-title":"Fundam Inform"},{"key":"9861_CR19","doi-asserted-by":"crossref","unstructured":"Jan\u010dar P, Mr\u00e1z F, Pl\u00e1tek M, Vogel J (1995) Restarting automata. In: Reichel H (ed.) Fundamentals of Computation Theory, FCT, LNCS, vol. 965, pp. 283\u2013292","DOI":"10.1007\/3-540-60249-6_60"},{"key":"9861_CR20","unstructured":"Kari L (1991) On insertion and deletion in formal languages. Ph.D. thesis, University of Turku"},{"key":"9861_CR21","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1080\/00207169408804288","volume":"52","author":"L Kari","year":"1994","unstructured":"Kari L (1994) Deletion operations: closure properties. Int J Comput Math 52:23\u201342","journal-title":"Int J Comput Math"},{"key":"9861_CR22","doi-asserted-by":"crossref","unstructured":"Kari L, P\u0103un Gh, Thierrin G, Yu S (1999) At the crossroads of DNA computing and formal languages: Characterizing recursively enumerable languages using insertion-deletion systems. In: Rubin H,  Wood DH (eds.) DNA Based Computers III, DIMACS Series in Discrete Mathematics and Theretical Computer Science, vol.\u00a048, pp. 329\u2013338. AMS","DOI":"10.1090\/dimacs\/048\/23"},{"issue":"1\u20133","key":"9861_CR23","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, Sos\u00edk P (2008) On the weight of universal insertion grammars. Theor Comput Sci 396(1\u20133):264\u2013270","journal-title":"Theor Comput Sci"},{"issue":"1","key":"9861_CR24","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"},{"key":"9861_CR25","unstructured":"Krassovitskiy A, Rogozhin Y, Verlan S (2008) Further results on insertion-deletion systems with one-sided contexts. In: \u00a0Mart\u00edn-Vide C, Otto F, \u00a0Fernau (eds.) Language and Automata Theory and Applications, Second International Conference, LATA 2008, Tarragona, Spain, March 13-19, 2008. Revised Papers, Lecture Notes in Computer Science, Springer, Berlin"},{"issue":"2","key":"9861_CR26","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1007\/s11047-010-9208-y","volume":"10","author":"A Krassovitskiy","year":"2011","unstructured":"Krassovitskiy A, Rogozhin Y, Verlan S (2011) Computational power of insertion-deletion (P) systems with rules of size two. Nat Comput 10(2):835\u2013852","journal-title":"Nat Comput"},{"key":"9861_CR27","unstructured":"Kuppusamy L, Mahendran A, Krishna SN (2011) Matrix insertion-deletion systems for bio-molecular structures. In: Natarajan R,  Ojo AK (eds.) Distributed Computing and Internet Technology - 7th International Conference, ICDCIT 2011, Bhubaneshwar, India, February 9-12, 2011. Proceedings, Lecture Notes in Computer Science, Springer, Berlin"},{"key":"9861_CR28","doi-asserted-by":"crossref","unstructured":"Marcus S (1969) Contextual grammars. In: Third International Conference on Computational Linguistics, COLING 1969, Stockholm, Sweden, September 1-4, 1969","DOI":"10.3115\/990403.990451"},{"issue":"2","key":"9861_CR29","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 (2005) Context-free insertion-deletion systems. Theor Comput Sci 330(2):339\u2013348","journal-title":"Theor Comput Sci"},{"key":"9861_CR30","unstructured":"Matveevici A, Rogozhin Y, Verlan S (2007) Insertion-deletion systems with one-sided contexts. In: Durand-Lose J O, Margenstern M (eds.) Machines, Computations, and Universality, 5th International Conference, MCU, LNCS, Springer, Berlin"},{"key":"9861_CR31","volume-title":"Computations: finite and infinite machines","author":"M Minsky","year":"1967","unstructured":"Minsky M (1967) Computations: finite and infinite machines. Prentice Hall, Englewood Cliffts, NJ"},{"key":"9861_CR32","doi-asserted-by":"crossref","unstructured":"Motwani R, Panigrahy R, Saraswat V, Ventkatasubramanian S (2000) On the decidability of accessibility problems (extended abstract). In: Proceedings of the Thirty-second Annual ACM Symposium on Theory of Computing, STOC, pp. 306\u2013315. ACM","DOI":"10.1145\/335305.335341"},{"issue":"1\u20134","key":"9861_CR33","first-page":"317","volume":"64","author":"M Mutyam","year":"2005","unstructured":"Mutyam M, Krithivasan K, Reddy AS (2005) On characterizing recursively enumerable languages by insertion grammars. Fundam Inform 64(1\u20134):317\u2013324","journal-title":"Fundam Inform"},{"issue":"5","key":"9861_CR34","first-page":"1424","volume":"44","author":"K Onodera","year":"2003","unstructured":"Onodera K (2003) A note on homomorphic representation of recursively enumerable languages with insertion grammars. Transac Inf Process Soc Japan 44(5):1424\u20131427","journal-title":"Transac Inf Process Soc Japan"},{"issue":"4","key":"9861_CR35","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1142\/S0129054108006005","volume":"19","author":"G P\u0103un","year":"2008","unstructured":"P\u0103un G, P\u00e9rez-Jim\u00e9nez MJ, Yokomori T (2008) Representations and characterizations of languages in chomsky hierarchy by means of insertion-deletion systems. Int J Found Comput Sci 19(4):859\u2013871. https:\/\/doi.org\/10.1142\/S0129054108006005","journal-title":"Int J Found Comput Sci"},{"key":"9861_CR36","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/j.tcs.2012.07.002","volume":"456","author":"I Petre","year":"2012","unstructured":"Petre I, Verlan S (2012) Matrix insertion-deletion systems. Theor Comput Sci 456:80\u201388. https:\/\/doi.org\/10.1016\/j.tcs.2012.07.002","journal-title":"Theor Comput Sci"},{"key":"9861_CR37","doi-asserted-by":"crossref","unstructured":"Potapov I, Prianychnykova O, Verlan S (2016) Insertion-deletion systems over relational words. In: K.G. Larsen, I.\u00a0Potapov, J.\u00a0Srba (eds.) Reachability Problems - 10th International Workshop, RP 2016, Aalborg, Denmark, September 19-21, 2016, Proceedings, Lecture Notes in Computer Science, Springer, Berlin","DOI":"10.1007\/978-3-319-45994-3_13"},{"key":"9861_CR38","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(85)90056-8","volume":"41","author":"Gh P\u0103un","year":"1985","unstructured":"P\u0103un Gh (1985) A variant of random context grammars: semi-conditional grammars. Theor Comput Sci 41:1\u201317. https:\/\/doi.org\/10.1016\/0304-3975(85)90056-8","journal-title":"Theor Comput Sci"},{"key":"9861_CR39","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 (1998) DNA computing: new computing paradigms. Springer, Berlin"},{"issue":"11","key":"9861_CR40","doi-asserted-by":"publisher","first-page":"2281","DOI":"10.1038\/nprot.2013.143","volume":"8","author":"FA Ran","year":"2013","unstructured":"Ran FA, Hsu PD, Wright J, Agarwala V, Scott DA, Zhang F (2013) Genome engineering using the CRISPR-Cas9 system. Nat Protocols 8(11):2281\u20132308. https:\/\/doi.org\/10.1038\/nprot.2013.143","journal-title":"Nat Protocols"},{"key":"9861_CR41","doi-asserted-by":"crossref","unstructured":"Rozenberg G, Salomaa A (eds) (1997) Handbook of Formal Languages. Springer-Verlag, Berlin","DOI":"10.1007\/978-3-642-59126-6"},{"issue":"4","key":"9861_CR42","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1023\/B:NACO.0000006769.27984.23","volume":"2","author":"A Takahara","year":"2003","unstructured":"Takahara A, Yokomori T (2003) On the computational power of insertion-deletion systems. Nat Comput 2(4):321\u2013336","journal-title":"Nat Comput"},{"issue":"1\u20132","key":"9861_CR43","first-page":"317","volume":"12","author":"S Verlan","year":"2007","unstructured":"Verlan S (2007) On minimal context-free insertion-deletion systems. J Automata, Lang Comb 12(1\u20132):317\u2013328","journal-title":"J Automata, Lang Comb"},{"issue":"2","key":"9861_CR44","first-page":"210","volume":"18","author":"S Verlan","year":"2010","unstructured":"Verlan S (2010) Recent developments on insertion-deletion systems. Comput Sci J Moldova 18(2):210\u2013245","journal-title":"Comput Sci J Moldova"},{"key":"9861_CR45","volume-title":"Theory of computation","author":"D Wood","year":"1987","unstructured":"Wood D (1987) Theory of computation. Harper and Row, NewYork"}],"container-title":["Natural Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-021-09861-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11047-021-09861-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-021-09861-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,18]],"date-time":"2021-11-18T04:55:24Z","timestamp":1637211324000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11047-021-09861-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,18]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["9861"],"URL":"https:\/\/doi.org\/10.1007\/s11047-021-09861-3","relation":{},"ISSN":["1567-7818","1572-9796"],"issn-type":[{"value":"1567-7818","type":"print"},{"value":"1572-9796","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,18]]},"assertion":[{"value":"21 June 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 July 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"On behalf of all authors, the corresponding author states that there is no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}