{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:12:46Z","timestamp":1759637566570,"version":"3.41.0"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319231105"},{"type":"electronic","value":"9783319231112"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[[2015]]},"DOI":"10.1007\/978-3-319-23111-2_6","type":"book-chapter","created":{"date-parts":[[2015,8,29]],"date-time":"2015-08-29T01:35:55Z","timestamp":1440812155000},"page":"79-93","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Universality of Graph-controlled Leftist Insertion-deletion Systems with Two States"],"prefix":"10.1007","author":[{"given":"Sergiu","family":"Ivanov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sergey","family":"Verlan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,8,30]]},"reference":[{"key":"6_CR1","volume-title":"RNA Editing: The Alteration of Protein Coding Sequences of RNA","author":"R Benne","year":"1993","unstructured":"Benne, R.: RNA Editing: The Alteration of Protein Coding Sequences of RNA. Ellis Horwood, Chichester, West Sussex (1993)"},{"issue":"2","key":"6_CR2","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, M.J., Daley, M.: Regulated RNA rewriting: modelling RNA editing with guided insertion. Theoret. Comput. Sci. 387(2), 103\u2013112 (2007)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"6_CR3","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1145\/321203.321206","volume":"11","author":"J Cocke","year":"1964","unstructured":"Cocke, J., Minsky, M.: Universality of tag systems with P = 2. J. ACM 11(1), 15\u201320 (1964)","journal-title":"J. ACM"},{"doi-asserted-by":"crossref","unstructured":"Daley, M., Kari, L., Gloor, G., Siromoney, R.: Circular contextual insertions\/deletions with applications to biomolecular computation. In: SPIRE\/CRIWG, pp. 47\u201354 (1999)","key":"6_CR4","DOI":"10.1109\/SPIRE.1999.796577"},{"doi-asserted-by":"crossref","unstructured":"Freund, R., Kogler, M., Rogozhin, Y., Verlan, S.: Graph-controlled insertion-deletion systems. In: McQuillan, I., Pighizzini, G. (eds.) Proceedings of the Twelfth Annual Workshop on Descriptional Complexity of Formal Systems, vol. 31 of EPTCS, pp. 88\u201398 (2010)","key":"6_CR5","DOI":"10.4204\/EPTCS.31.11"},{"unstructured":"Galiukschov, B.: Semicontextual grammars. Matematicheskaya Logica i Matematicheskaya Lingvistika, pp. 38\u201350. Tallin University, Russian (1981)","key":"6_CR6"},{"unstructured":"Haussler, D.: Insertion and Iterated Insertion as Operations on Formal Languages. PhD thesis, University of Colorado at Boulder (1982)","key":"6_CR7"},{"issue":"1","key":"6_CR8","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.: Insertion languages. Inf. Sci. 31(1), 77\u201389 (1983)","journal-title":"Inf. Sci."},{"unstructured":"Ivanov, S., Verlan, S.: On the lower bounds for leftist insertion-deletion languages. Submitted","key":"6_CR9"},{"unstructured":"Ivanov, S., Verlan, S.: Random context and semi-conditional insertion-deletion systems. CoRR, abs\/1112.5947 (2011)","key":"6_CR10"},{"key":"6_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/978-3-642-54239-8_16","volume-title":"Membrane Computing","author":"S Ivanov","year":"2014","unstructured":"Ivanov, S., Verlan, S.: About one-sided one-symbol insertion-deletion P systems. In: Alhazov, A., Cojocaru, S., Gheorghe, M., Rogozhin, Y., Rozenberg, G., Salomaa, A. (eds.) CMC 2013. LNCS, vol. 8340, pp. 225\u2013237. Springer, Heidelberg (2014)"},{"unstructured":"Kari, L.: On insertion and deletion in formal languages. PhD thesis, University of Turku (1991)","key":"6_CR12"},{"unstructured":"Kari, L., P\u0103un, G., Thierrin, G., Yu, S.: At the crossroads of DNA computing and formal languages: characterizing RE using insertion-deletion systems. In: Proceedings of 3rd DIMACS Workshop on DNA Based Computing, pp. 318\u2013333. Philadelphia (1997)","key":"6_CR13"},{"issue":"1","key":"6_CR14","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.: Contextual insertions\/deletions and computability. Inf. Comput. 131(1), 47\u201361 (1996)","journal-title":"Inf. Comput."},{"key":"6_CR15","first-page":"3","volume-title":"Automata Studies","author":"SC Kleene","year":"1956","unstructured":"Kleene, S.C.: Representation of events in nerve nets and finite automata. In: Shannon, C., McCarthy, J. (eds.) Automata Studies, pp. 3\u201341. Princeton University Press, Princeton, NJ (1956)"},{"unstructured":"Krassovitskiy, A.: Complexity and Modeling Power of Insertion-Deletion Systems. PhD thesis, Departament de Filologies Rom\u00e1niques, Universitat Rovira and Virgili (2011)","key":"6_CR16"},{"key":"6_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/978-3-540-88282-4_31","volume-title":"Language and Automata Theory and Applications","author":"A Krassovitskiy","year":"2008","unstructured":"Krassovitskiy, A., Rogozhin, Y., Verlan, S.: Further results on insertion-deletion systems with one-sided contexts. In: Mart\u00edn-Vide, C., Otto, F., Fernau, H. (eds.) LATA 2008. LNCS, vol. 5196, pp. 333\u2013344. Springer, Heidelberg (2008)"},{"issue":"2","key":"6_CR18","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.: Computational power of insertion deletion (P) systems with rules of size two. Nat. Comput. 10(2), 835\u2013852 (2011)","journal-title":"Nat. Comput."},{"key":"6_CR19","first-page":"1525","volume":"14","author":"S Marcus","year":"1969","unstructured":"Marcus, S.: Contextual grammars. Revue Roumaine de Math\u00e9matiques Pures et Appliqu\u00e9es 14, 1525\u20131534 (1969)","journal-title":"Revue Roumaine de Math\u00e9matiques Pures et Appliqu\u00e9es"},{"issue":"2","key":"6_CR20","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, G., Rogozhin, Y., Verlan, S.: Context-free insertion-deletion systems. Theoret. Comput. Sci. 330(2), 339\u2013348 (2005)","journal-title":"Theoret. Comput. Sci."},{"key":"6_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/978-3-540-74593-8_18","volume-title":"Machines, Computations, and Universality","author":"A Matveevici","year":"2007","unstructured":"Matveevici, A., Rogozhin, Y., Verlan, S.: Insertion-deletion systems with one-sided contexts. In: Durand-Lose, J., Margenstern, M. (eds.) MCU 2007. LNCS, vol. 4664, pp. 205\u2013217. Springer, Heidelberg (2007)"},{"key":"6_CR22","volume-title":"Computations: Finite and Infinite Machines","author":"M Minsky","year":"1967","unstructured":"Minsky, M.: Computations: Finite and Infinite Machines. Prentice Hall, Englewood Cliffts, NJ (1967)"},{"key":"6_CR23","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.: Matrix insertion-deletion systems. Theoret. Comput. Sci. 456, 80\u201388 (2012)","journal-title":"Theoret. Comput. Sci."},{"key":"6_CR24","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-015-8969-7","volume-title":"Marcus Contextual Grammars","author":"G P\u0103un","year":"1997","unstructured":"P\u0103un, G.: Marcus Contextual Grammars. Kluwer Academic Publishers, Norwell, MA, USA (1997)"},{"key":"6_CR25","first-page":"641","volume":"25","author":"G P\u0103un","year":"1980","unstructured":"P\u0103un, G., My, N.X.: On the inner contextual grammars. Revue Roumaine de Math\u00e9matiques Pures et Appliqu\u00e9es 25, 641\u2013651 (1980)","journal-title":"Revue Roumaine de Math\u00e9matiques Pures et Appliqu\u00e9es"},{"key":"6_CR26","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03563-4","volume-title":"DNA Computing: New Computing Paradigms","author":"G P\u0103un","year":"1998","unstructured":"P\u0103un, G., Rozenberg, G., Salomaa, A.: DNA Computing: New Computing Paradigms. Springer, Heidelberg (1998)"},{"volume-title":"Handbook of Formal Languages","year":"1997","unstructured":"Rozenberg, G., Salomaa, A. (eds.): Handbook of Formal Languages. Springer-Verlag, Berlin (1997)","key":"6_CR27"},{"key":"6_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/3-540-36440-4_24","volume-title":"DNA Computing","author":"A Takahara","year":"2002","unstructured":"Takahara, A., Yokomori, T.: On the computational power of insertion-deletion systems. In: Hagiya, M., Ohuchi, A. (eds.) DNA8 Sapporo. LNCS, vol. 2568, pp. 269\u2013280. Springer, Heidelberg (2002)"},{"issue":"1\u20132","key":"6_CR29","first-page":"317","volume":"12","author":"S Verlan","year":"2007","unstructured":"Verlan, S.: On minimal context-free insertion-deletion systems. J. Automata, Languages Comb. 12(1\u20132), 317\u2013328 (2007)","journal-title":"J. Automata, Languages Comb."},{"unstructured":"Verlan, S.: Study of language-theoretic computational paradigms inspired by biology. Habilitation thesis, Universit\u00e9 Paris Est (2010)","key":"6_CR30"}],"container-title":["Lecture Notes in Computer Science","Machines, Computations, and Universality"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-23111-2_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,30]],"date-time":"2025-05-30T08:21:40Z","timestamp":1748593300000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-23111-2_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319231105","9783319231112"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-23111-2_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"30 August 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}