{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,12]],"date-time":"2025-12-12T09:18:01Z","timestamp":1765531081193,"version":"3.48.0"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T00:00:00Z","timestamp":1761264000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T00:00:00Z","timestamp":1761264000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100009232","name":"University of Debrecen","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100009232","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2025,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>We investigate the relationship of languages characterized by variants of string assembling systems and by Watson-Crick finite automata with a small number of states. Besides the general variant, we consider so-called free, and pure string assembling systems and compare their language generating power to Watson-Crick finite automata having one state (also called stateless) and two or three states in their state sets. We also study restricted variants of models that describe unary languages.<\/jats:p>","DOI":"10.1007\/s00236-025-00510-1","type":"journal-article","created":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T09:44:20Z","timestamp":1761299060000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Watson-Crick finite automata of small size and variants of string assembling systems"],"prefix":"10.1007","volume":"62","author":[{"given":"Andr\u00e1s","family":"Murvai","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gy\u00f6rgy","family":"Vaszil","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,10,24]]},"reference":[{"key":"510_CR1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-54943-5","volume-title":"Numerical Semigroups and Applications","author":"A Assi","year":"2020","unstructured":"Assi, A., D\u2019Anna, M., Garc\u00eda-S\u00e1nchez, P.A.: Numerical Semigroups and Applications. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-54943-5"},{"issue":"35","key":"510_CR2","doi-asserted-by":"publisher","first-page":"3250","DOI":"10.1016\/j.tcs.2009.05.001","volume":"410","author":"E Czeizler","year":"2009","unstructured":"Czeizler, E., Czeizler, E., Kari, L., Salomaa, K.: On the descriptional complexity of Watson-Crick automata. Theoret. Comput. Sci. 410(35), 3250\u20133260 (2009). https:\/\/doi.org\/10.1016\/j.tcs.2009.05.001","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"510_CR3","first-page":"685","volume":"17","author":"E Czeizler","year":"2006","unstructured":"Czeizler, E., Czeizler, E.: Parallel communicating Watson-Crick automata systems. Acta Cybernet. 17(4), 685\u2013700 (2006)","journal-title":"Acta Cybernet."},{"issue":"1","key":"510_CR4","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1016\/j.tcs.2006.01.049","volume":"358","author":"E Czeizler","year":"2006","unstructured":"Czeizler, E., Czeizler, E.: On the power of parallel communicating Watson-Crick automata systems. Theoret. Comput. Sci. 358(1), 142\u2013147 (2006). https:\/\/doi.org\/10.1016\/j.tcs.2006.01.049","journal-title":"Theoret. Comput. Sci."},{"key":"510_CR5","doi-asserted-by":"publisher","unstructured":"Freund, R., P\u0103un, G., Rozenberg, G., Salomaa, A.: Watson-Crick finite automata. In: Rubin, H., Wood, D.H. (eds.) DNA Based Computers, Proceedings of a DIMACS Workshop. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 48, pp. 297\u2013327. DIMACS\/AMS, (1997). https:\/\/doi.org\/10.1090\/dimacs\/048\/22","DOI":"10.1090\/dimacs\/048\/22"},{"key":"510_CR6","doi-asserted-by":"publisher","unstructured":"Kari, L., Seki, S., Sos\u00edk, P.: DNA computing - foundations and implications. In: Rozenberg, G., B\u00e4ck, T., Kok, J.N. (eds.) Handbook of Natural Computing, pp. 1073\u20131127. Springer, Berlin, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-540-92910-9_33","DOI":"10.1007\/978-3-540-92910-9_33"},{"issue":"5","key":"510_CR7","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/s002360050125","volume":"35","author":"L Kari","year":"1998","unstructured":"Kari, L., P\u0103un, G., Rozenberg, G., Salomaa, A., Yu, S.: DNA computing, sticker systems, and universality. Acta Informatica 35(5), 401\u2013420 (1998). https:\/\/doi.org\/10.1007\/s002360050125","journal-title":"Acta Informatica"},{"issue":"4","key":"510_CR8","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1051\/ita\/2012020","volume":"46","author":"M Kutrib","year":"2012","unstructured":"Kutrib, M., Wendlandt, M.: String assembling systems. RAIRO - Theoretical Informatics and Applications 46(4), 593\u2013613 (2012). https:\/\/doi.org\/10.1051\/ita\/2012020","journal-title":"RAIRO - Theoretical Informatics and Applications"},{"key":"510_CR9","doi-asserted-by":"publisher","unstructured":"Kuske, D., Weigel, P.: The role of the complementarity relation in Watson-Crick automata and sticker systems. In: Calude, C., Calude, E., Dinneen, M.J. (eds.) Developments in Language Theory, 8th International Conference, DLT 2004, Proceedings. Lecture Notes in Computer Science, vol. 3340, pp. 272\u2013283. Springer, Berlin, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-30550-7_23","DOI":"10.1007\/978-3-540-30550-7_23"},{"key":"510_CR10","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/s11047-022-09918-x","volume":"23","author":"M Kutrib","year":"2024","unstructured":"Kutrib, M., Wendlandt, M.: Variants of string assembling systems. Natural Computing 23, 131\u2013156 (2024). https:\/\/doi.org\/10.1007\/s11047-022-09918-x","journal-title":"Natural Computing"},{"key":"510_CR11","doi-asserted-by":"publisher","unstructured":"Murvai, A., Vaszil, G.: On the power of small Watson-Crick automata and variants of string assembling systems. In: Formenti, E., Durand-Lose, J. (eds.) Machines, Computations, and Universality. MCU 2024. Lecture Notes in Computer Science, vol. 15270, pp. 89\u2013102. Springer, Cham (2025). https:\/\/doi.org\/10.1007\/978-3-031-81202-6_6","DOI":"10.1007\/978-3-031-81202-6_6"},{"key":"510_CR12","unstructured":"Murvai, A., Vaszil, G.: String assembling systems and Watson-Crick finite automata. In: Brejov\u00e1, B., Ciencialov\u00e1, L., Holena, M., Mr\u00e1z, F., Pardubsk\u00e1, D., Pl\u00e1tek, M., Vinar, T. (eds.) Proceedings of the 21st Conference Information Technologies - Applications and Theory (ITAT 2021). CEUR Workshop Proceedings, vol. 2962, pp. 210\u2013216. CEUR-WS.org (2021). https:\/\/ceur-ws.org\/Vol-2962\/paper44.pdf"},{"key":"510_CR13","doi-asserted-by":"publisher","unstructured":"P\u0103un, G., Rozenberg, G., Salomaa, A.: DNA Computing - New Computing Paradigms. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin Heidelberg (1998). https:\/\/doi.org\/10.1007\/978-3-662-03563-4","DOI":"10.1007\/978-3-662-03563-4"},{"key":"510_CR14","doi-asserted-by":"publisher","unstructured":"Rozenberg, G., Salomaa, A. (eds.): Handbook of Formal Languages, Volume 1: Word, Language, Grammar. Springer, Berlin, Heidelberg (1997). https:\/\/doi.org\/10.1007\/978-3-642-59136-5","DOI":"10.1007\/978-3-642-59136-5"},{"key":"510_CR15","volume-title":"Formal Languages","author":"A Salomaa","year":"1973","unstructured":"Salomaa, A.: Formal Languages. Academic Press, New York (1973)"},{"key":"510_CR16","doi-asserted-by":"publisher","DOI":"10.3390\/math9080813","author":"JM Sempere","year":"2021","unstructured":"Sempere, J.M.: On the languages accepted by Watson-Crick finite automata with delays. Mathematics (2021). https:\/\/doi.org\/10.3390\/math9080813","journal-title":"Mathematics"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-025-00510-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-025-00510-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-025-00510-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,12]],"date-time":"2025-12-12T09:14:13Z","timestamp":1765530853000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-025-00510-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,24]]},"references-count":16,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["510"],"URL":"https:\/\/doi.org\/10.1007\/s00236-025-00510-1","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"type":"print","value":"0001-5903"},{"type":"electronic","value":"1432-0525"}],"subject":[],"published":{"date-parts":[[2025,10,24]]},"assertion":[{"value":"2 December 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 September 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 October 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"39"}}