{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,18]],"date-time":"2025-12-18T20:01:51Z","timestamp":1766088111640,"version":"3.37.3"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,8,29]],"date-time":"2023-08-29T00:00:00Z","timestamp":1693267200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,8,29]],"date-time":"2023-08-29T00:00:00Z","timestamp":1693267200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100010629","name":"Silesian University in Opava","doi-asserted-by":"crossref","award":["SGS\/11\/2023"],"award-info":[{"award-number":["SGS\/11\/2023"]}],"id":[{"id":"10.13039\/501100010629","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100010629","name":"Silesian University in Opava","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100010629","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Membr Comput"],"published-print":{"date-parts":[[2023,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Watson-Crick L systems are string generating formal models obtained by augmenting Lindenmayer systems with the <jats:italic>Watson-Crick morphism<\/jats:italic> inspired by the Watson-Crick complementarity principle. The Watson-Crick morphism is controlled by a <jats:italic>trigger<\/jats:italic>\u2014a boolean condition eventually met by the generated word. Despite their simplicity, Watson-Crick (D)0\u00a0L systems have interesting mathematical properties, a strong generative power, and they can also characterize some open decision problems. Furthermore, networks of Watson-Crick D0L systems are capable of trading space for time, and thus of characterizing linear time solutions to intractable problems. We provide a survey of results in this field since its origin in 1997 to the present, and we conclude with a series of open research problems and ideas.<\/jats:p>","DOI":"10.1007\/s41965-023-00130-z","type":"journal-article","created":{"date-parts":[[2023,8,29]],"date-time":"2023-08-29T15:03:18Z","timestamp":1693321398000},"page":"182-189","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Watson-crick (D)0\u00a0L systems: a survey"],"prefix":"10.1007","volume":"5","author":[{"given":"Petr","family":"Sos\u00edk","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,8,29]]},"reference":[{"issue":"3","key":"130_CR1","doi-asserted-by":"publisher","first-page":"1665","DOI":"10.1016\/S0304-3975(02)00074-9","volume":"290","author":"J Csima","year":"2003","unstructured":"Csima, J., Csuhaj-Varj\u00fa, E., & Salomaa, A. (2003). Power and size of extended Watson-Crick L systems. Theoretical Computer Science, 290(3), 1665\u20131678.","journal-title":"Theoretical Computer Science"},{"unstructured":"Csuhaj-Varj\u00fa, E.: Watson-Crick complementarity, L systems, computation. In: Durand-Lose, J., Verlan, S. (eds.) Machines, Computations, and Universality: 8th International Conference. Lecture Notes in Computer Science, vol. 10881. Springer, Cham (2018). pp. XI\u2013XII","key":"130_CR2"},{"key":"130_CR3","first-page":"42","volume-title":"Algebraic Systems, Formal Languages and Computations","author":"E Csuhaj-Varj\u00fa","year":"2000","unstructured":"Csuhaj-Varj\u00fa, E. (2000). Computing by networks of standard Watson-Crick D0L systems. In M. Ito (Ed.), Algebraic Systems, Formal Languages and Computations (Vol. 1166, pp. 42\u201351). Kyoto University, Research Institute for Mathematical Sciences."},{"key":"130_CR4","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/978-3-540-27812-2_4","volume-title":"Theory Is Forever","author":"E Csuhaj-Varj\u00fa","year":"2004","unstructured":"Csuhaj-Varj\u00fa, E. (2004). Networks of standard Watson-Crick D0L systems with incomplete information communication. In J. Karhum\u00e4ki, H. Maurer, G. P\u0103un, & G. Rozenberg (Eds.), Theory Is Forever (pp. 35\u201348). Cham: Springer."},{"issue":"1\u20132","key":"130_CR5","doi-asserted-by":"publisher","first-page":"111","DOI":"10.3233\/FI-2017-1578","volume":"155","author":"E Csuhaj-Varj\u00fa","year":"2017","unstructured":"Csuhaj-Varj\u00fa, E., Freund, R., & Vaszil, G. (2017). Watson-Crick T0L systems and red-green register machines. Fundamenta Informaticae, 155(1\u20132), 111\u2013129.","journal-title":"Fundamenta Informaticae"},{"issue":"3","key":"130_CR6","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1023\/A:1025415914487","volume":"2","author":"E Csuhaj-Varj\u00fa","year":"2003","unstructured":"Csuhaj-Varj\u00fa, E., Mart\u00edn-Vide, C., P\u0103un, G., & Salomaa, A. (2003). From Watson-Crick L systems to Darwinian P systems. Natural Computing, 2(3), 299\u2013318.","journal-title":"Natural Computing"},{"key":"130_CR7","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1142\/9789812704979_0009","volume-title":"Words, Languages & Combinatorics III","author":"E Csuhaj-Varj\u00fa","year":"2003","unstructured":"Csuhaj-Varj\u00fa, E., & Salomaa, A. (2003). Networks of Watson-Crick D0L systems. In M. Ito & T. Imaoka (Eds.), Words, Languages & Combinatorics III (pp. 134\u2013150). Singapore: World Scientific."},{"key":"130_CR8","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1007\/978-3-540-24635-0_7","volume-title":"Aspects of Molecular Computing","author":"E Csuhaj-Varj\u00fa","year":"2003","unstructured":"Csuhaj-Varj\u00fa, E., & Salomaa, A. (2003). The power of networks of Watson-Crick D0L systems. In N. Jonoska, G. P\u0103un, & G. Rozenberg (Eds.), Aspects of Molecular Computing (pp. 106\u2013118). Cham: Springer."},{"issue":"1\u20133","key":"130_CR9","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1016\/S0304-3975(03)00087-2","volume":"302","author":"J Honkala","year":"2003","unstructured":"Honkala, J. (2003). Decidability results for Watson-Crick D0L systems with nonregular triggers. Theoretical Computer Science, 302(1\u20133), 481\u2013488.","journal-title":"Theoretical Computer Science"},{"key":"130_CR10","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/j.tcs.2016.12.033","volume":"701","author":"J Honkala","year":"2017","unstructured":"Honkala, J. (2017). Discrete Watson-Crick dynamical systems. Theoretical Computer Science, 701, 125\u2013131.","journal-title":"Theoretical Computer Science"},{"issue":"1\u20132","key":"130_CR11","doi-asserted-by":"publisher","first-page":"689","DOI":"10.1016\/S0304-3975(01)00010-X","volume":"259","author":"J Honkala","year":"2001","unstructured":"Honkala, J., & Salomaa, A. (2001). Watson-Crick D0L systems with regular triggers. Theoretical Computer Science, 259(1\u20132), 689\u2013698.","journal-title":"Theoretical Computer Science"},{"unstructured":"Kuich, W., Salomaa, A.: Semirings, Automata, Languages. EATCS monographs on theoretical computer science, vol. 5. Springer, Cham (2012)","key":"130_CR12"},{"key":"130_CR13","first-page":"160","volume":"62","author":"V Mihalache","year":"1997","unstructured":"Mihalache, V., & Salomaa, A. (1997). Watson-Crick D0L systems. EATCS Bulletin, 62, 160\u2013175.","journal-title":"EATCS Bulletin"},{"issue":"1\u20132","key":"130_CR14","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/S0304-3975(99)00129-2","volume":"250","author":"V Mihalache","year":"2001","unstructured":"Mihalache, V., & Salomaa, A. (2001). Language-theoretic aspects of DNA complementarity. Theoretical Computer Science, 250(1\u20132), 163\u2013178.","journal-title":"Theoretical Computer Science"},{"key":"130_CR15","volume-title":"Handbook of Formal Languages","author":"G Rozenberg","year":"2012","unstructured":"Rozenberg, G., & Salomaa, A. (2012). Handbook of Formal Languages. Cham: Springer."},{"issue":"1","key":"130_CR16","first-page":"179","volume":"14","author":"A Salomaa","year":"1999","unstructured":"Salomaa, A. (1999). Watson-Crick walks and roads on dol graphs. Acta Cybernetica, 14(1), 179\u2013192.","journal-title":"Acta Cybernetica"},{"issue":"1\u20132","key":"130_CR17","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1016\/S0304-3975(02)00026-9","volume":"281","author":"A Salomaa","year":"2002","unstructured":"Salomaa, A. (2002). Uni-transitional Watson-Crick D0L systems. Theoretical Computer Science, 281(1\u20132), 537\u2013553.","journal-title":"Theoretical Computer Science"},{"key":"130_CR18","volume-title":"Automata-theoretic Aspects of Formal Power Series","author":"A Salomaa","year":"2012","unstructured":"Salomaa, A., & Soittola, M. (2012). Automata-theoretic Aspects of Formal Power Series. Cham: Springer."},{"issue":"1\u20133","key":"130_CR19","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/S0304-3975(02)00580-7","volume":"301","author":"A Salomaa","year":"2003","unstructured":"Salomaa, A., & Sos\u00edk, P. (2003). Watson-Crick D0L systems: the power of one transition. Theoretical Computer Science, 301(1\u20133), 187\u2013200.","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"130_CR20","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1007\/s11047-012-9329-6","volume":"11","author":"D Sears","year":"2012","unstructured":"Sears, D., & Salomaa, K. (2012). Extended Watson-Crick L systems with regular trigger languages and restricted derivation modes. Natural Computing, 11(4), 653\u2013664.","journal-title":"Natural Computing"},{"doi-asserted-by":"crossref","unstructured":"Sos\u00edk, P.: D0L system + Watson-Crick complementarity = universal computation. In: Machines, Computations, and Universality, Third International Conference. Lecture Notes in Computer Science, vol. 2055, pp. 308\u2013319 (2001). Springer","key":"130_CR21","DOI":"10.1007\/3-540-45132-3_22"},{"issue":"1","key":"130_CR22","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1016\/S0304-3975(01)00328-0","volume":"289","author":"P Sos\u0131k","year":"2002","unstructured":"Sos\u0131k, P. (2002). Universal computation with Watson-Crick D0L systems. Theoretical Computer Science, 289(1), 485\u2013501.","journal-title":"Theoretical Computer Science"},{"issue":"1\u20133","key":"130_CR23","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/S0304-3975(03)00214-7","volume":"306","author":"P Sos\u00edk","year":"2003","unstructured":"Sos\u00edk, P. (2003). Watson-Crick D0L systems: generative power and undecidable problems. Theoretical Computer Science, 306(1\u20133), 101\u2013112.","journal-title":"Theoretical Computer Science"}],"container-title":["Journal of Membrane Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41965-023-00130-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41965-023-00130-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41965-023-00130-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,22]],"date-time":"2023-09-22T13:15:10Z","timestamp":1695388510000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s41965-023-00130-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,29]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["130"],"URL":"https:\/\/doi.org\/10.1007\/s41965-023-00130-z","relation":{},"ISSN":["2523-8906","2523-8914"],"issn-type":[{"type":"print","value":"2523-8906"},{"type":"electronic","value":"2523-8914"}],"subject":[],"published":{"date-parts":[[2023,8,29]]},"assertion":[{"value":"5 January 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 August 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 August 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}