{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,18]],"date-time":"2026-09-18T02:30:27Z","timestamp":1789698627252,"version":"4.0.1"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032284037","type":"print"},{"value":"9783032284044","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"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":[[2026]]},"DOI":"10.1007\/978-3-032-28404-4_5","type":"book-chapter","created":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T23:21:00Z","timestamp":1780701660000},"page":"57-71","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Self-assembly of\u00a0Strings and\u00a0Languages Revisited: Efficiently Deciding Closure Under Self-assembly"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9386-7372","authenticated-orcid":false,"given":"Katalin Anna","family":"L\u00e1z\u00e1r","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6094-3324","authenticated-orcid":false,"given":"Florin","family":"Manea","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7509-8135","authenticated-orcid":false,"given":"Stefan","family":"Siemer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-0175-8345","authenticated-orcid":false,"given":"Timo","family":"Specht","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,6,6]]},"reference":[{"key":"5_CR1","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms, Addison-Wesley (1974)"},{"issue":"1","key":"5_CR2","doi-asserted-by":"publisher","first-page":"69","DOI":"10.4086\/toc.2012.v008a004","volume":"8","author":"N Bansal","year":"2012","unstructured":"Bansal, N., Williams, R.: Regularity lemmas and combinatorial algorithms. Theory Comput. 8(1), 69\u201394 (2012)","journal-title":"Theory Comput."},{"key":"5_CR3","unstructured":"Belazzougui, D., Kosolobov, D., Puglisi, S.J., Raman, R.: Weighted ancestors in suffix trees revisited. In: 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021), vol. 191, pp. 8:1\u20138:15 (2021)"},{"issue":"4","key":"5_CR4","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1007\/s11047-021-09867-x","volume":"20","author":"F Bellamoli","year":"2021","unstructured":"Bellamoli, F., Franco, G., Kari, L., Lampis, S., Ng, T., Wang, Z.: Conjugate word blending: formal model and experimental implementation by XPCR. Nat. Comput. 20(4), 647\u2013658 (2021)","journal-title":"Nat. Comput."},{"issue":"4","key":"5_CR5","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1007\/s00224-004-1175-1","volume":"39","author":"P Bottoni","year":"2006","unstructured":"Bottoni, P., Labella, A., Manca, V., Mitrana, V.: Superposition based on Watson-Crick-like complementarity. Theory Comput. Syst. 39(4), 503\u2013524 (2006)","journal-title":"Theory Comput. Syst."},{"issue":"8","key":"5_CR6","doi-asserted-by":"publisher","first-page":"1113","DOI":"10.1142\/S012905412042006X","volume":"31","author":"JA Brzozowski","year":"2020","unstructured":"Brzozowski, J.A., Kari, L., Li, B., Szyku\u0142a, M.: State complexity of overlap assembly. Int. J. Found. Comput. Sci. 31(8), 1113\u20131132 (2020)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"1\u20132","key":"5_CR7","first-page":"41","volume":"21","author":"E Csuhaj-Varj\u00fa","year":"2016","unstructured":"Csuhaj-Varj\u00fa, E., L\u00e1z\u00e1r, K.A.: String assembly in networks of evolutionary processors. J. Autom. Lang. Comb. 21(1\u20132), 41\u201354 (2016)","journal-title":"J. Autom. Lang. Comb."},{"issue":"1","key":"5_CR8","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1016\/j.tcs.2006.12.004","volume":"374","author":"E Csuhaj-Varj\u00fa","year":"2007","unstructured":"Csuhaj-Varj\u00fa, E., Petre, I., Vaszil, G.: Self-assembly of strings and languages. Theor. Comput. Sci. 374(1), 74\u201381 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"5_CR9","unstructured":"Das, D., Kouck\u00fd, M., Saks, M.E.: Lower bounds for combinatorial algorithms for Boolean Matrix Multiplication. In: STACS. LIPIcs, vol. 96, pp. 23:1\u201323:14 (2018)"},{"issue":"1","key":"5_CR10","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/j.ic.2017.01.009","volume":"253","author":"SK Enaganti","year":"2017","unstructured":"Enaganti, S.K., Ibarra, O.H., Kari, L., Kopecki, S.: Further remarks on DNA overlap assembly. Inf. Comput. 253(1), 143\u2013154 (2017)","journal-title":"Inf. Comput."},{"key":"5_CR11","doi-asserted-by":"crossref","unstructured":"Enaganti, S.K., Ibarra, O.H., Kari, L., Kopecki, S.: On the overlap assembly of strings and languages. Nat. Comput. 1\u201311 (2017)","DOI":"10.1007\/s11047-015-9538-x"},{"issue":"1\u20134","key":"5_CR12","first-page":"151","volume":"171","author":"SK Enaganti","year":"2020","unstructured":"Enaganti, S.K., Kari, L., Ng, T., Wang, Z.: Word blending in formal languages. Fundam. Inform. 171(1\u20134), 151\u2013173 (2020)","journal-title":"Fundam. Inform."},{"key":"5_CR13","doi-asserted-by":"crossref","unstructured":"Farach, M.: Optimal suffix tree construction with large alphabets. In: 38th Annual Symposium on Foundations of Computer Science, FOCS 1997, Miami Beach, Florida, USA, October 19\u201322, 1997. pp. 137\u2013143. IEEE Computer Society (1997)","DOI":"10.1109\/SFCS.1997.646102"},{"key":"5_CR14","doi-asserted-by":"crossref","unstructured":"Fredman, M.L., Willard, D.E.: BLASTING through the information theoretic barrier with FUSION TREES. In: Ortiz, H. (ed.) Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13\u201317, 1990, Baltimore, Maryland, USA, pp. 1\u20137. ACM (1990)","DOI":"10.1145\/100216.100217"},{"issue":"4","key":"5_CR15","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0020-0190(92)90176-V","volume":"41","author":"D Gusfield","year":"1992","unstructured":"Gusfield, D., Landau, G.M., Schieber, B.: An efficient algorithm for the all pairs suffix-prefix problem. Inf. Process. Lett. 41(4), 181\u2013185 (1992)","journal-title":"Inf. Process. Lett."},{"key":"5_CR16","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley (1979)"},{"issue":"1\u20132","key":"5_CR17","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1016\/j.ic.2010.11.014","volume":"209","author":"M Ito","year":"2011","unstructured":"Ito, M., Leupold, P., Manea, F., Mitrana, V.: Bounded hairpin completion. Inf. Comput. 209(1\u20132), 471\u2013485 (2011)","journal-title":"Inf. Comput."},{"issue":"6","key":"5_CR18","doi-asserted-by":"publisher","first-page":"918","DOI":"10.1145\/1217856.1217858","volume":"53","author":"J K\u00e4rkk\u00e4inen","year":"2006","unstructured":"K\u00e4rkk\u00e4inen, J., Sanders, P., Burkhardt, S.: Linear work suffix array construction. J. ACM 53(6), 918\u2013936 (2006)","journal-title":"J. ACM"},{"key":"5_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/3-540-48194-X_17","volume-title":"Combinatorial Pattern Matching","author":"T Kasai","year":"2001","unstructured":"Kasai, T., Lee, G., Arimura, H., Arikawa, S., Park, K.: Linear-time longest-common-prefix computation in suffix arrays and its applications. In: Amir, A. (ed.) CPM 2001. LNCS, vol. 2089, pp. 181\u2013192. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-48194-X_17"},{"issue":"2","key":"5_CR20","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"DE Knuth","year":"1977","unstructured":"Knuth, D.E., Morris, J.H., Jr., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput. 6(2), 323\u2013350 (1977)","journal-title":"SIAM J. Comput."},{"issue":"9","key":"5_CR21","doi-asserted-by":"publisher","first-page":"2143","DOI":"10.1016\/j.dam.2007.09.022","volume":"157","author":"F Manea","year":"2009","unstructured":"Manea, F., Mart\u00edn-Vide, C., Mitrana, V.: On some algorithmic problems regarding the hairpin completion. Discrete Appl. Math. 157(9), 2143\u20132152 (2009)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"5_CR22","doi-asserted-by":"publisher","first-page":"987","DOI":"10.1093\/logcom\/exs076","volume":"25","author":"F Manea","year":"2015","unstructured":"Manea, F., Mart\u00edn-Vide, C., Mitrana, V.: Hairpin lengthening: language theoretic and algorithmic results. J. Log. Comput. 25(4), 987\u20131009 (2015)","journal-title":"J. Log. Comput."},{"issue":"4\u20135","key":"5_CR23","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1016\/j.tcs.2008.09.049","volume":"410","author":"F Manea","year":"2009","unstructured":"Manea, F., Mitrana, V., Yokomori, T.: Two complementary operations inspired by the DNA hairpin formation: completion and reduction. Theor. Comput. Sci. 410(4\u20135), 417\u2013425 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"5_CR24","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1142\/S0129054110007593","volume":"21","author":"F Manea","year":"2010","unstructured":"Manea, F., Mitrana, V., Yokomori, T.: Some remarks on the hairpin completion. Int. J. Found. Comput. Sci. 21(5), 859\u2013872 (2010)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"5_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/978-3-030-48516-0_6","volume-title":"Developments in Language Theory","author":"M de Oliveira Oliveira","year":"2020","unstructured":"de Oliveira Oliveira, M., Wehar, M.: On the fine grained complexity of finite automata non-emptiness of intersection. In: Jonoska, N., Savchuk, D. (eds.) DLT 2020. LNCS, vol. 12086, pp. 69\u201382. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-48516-0_6"},{"key":"5_CR26","unstructured":"Park, S., Park, S.G., Cazaux, B., Park, K., Rivals, E.: A linear time algorithm for constructing hierarchical overlap graphs. In: 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021). Leibniz International Proceedings in Informatics (LIPIcs), vol. 191, pp. 22:1\u201322:9 (2021)"},{"key":"5_CR27","doi-asserted-by":"publisher","first-page":"837","DOI":"10.1142\/S0129054101000904","volume":"12","author":"G P\u0103un","year":"2001","unstructured":"P\u0103un, G., Rozenberg, G., Yokomori, T.: Hairpin languages. Int. J. Found. Comput. Sci. 12, 837\u2013847 (2001)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"22","key":"5_CR28","doi-asserted-by":"publisher","first-page":"10747","DOI":"10.1073\/pnas.91.22.10747","volume":"91","author":"WP Stemmer","year":"1994","unstructured":"Stemmer, W.P.: DNA shuffling by random fragmentation and reassembly: in vitro recombination for molecular evolution. Proc. Natl. Acad. Sci. 91(22), 10747\u201310751 (1994)","journal-title":"Proc. Natl. Acad. Sci."},{"key":"5_CR29","doi-asserted-by":"crossref","unstructured":"Vassilevska Williams, V.: On some fine-grained questions in algorithms and complexity. In: Proceedings of the International Congress of Mathematicians (ICM 2018), pp. 3447\u20133487. World Scientific (2018)","DOI":"10.1142\/9789813272880_0188"},{"key":"5_CR30","doi-asserted-by":"crossref","unstructured":"Vassilevska Williams, V., Williams, R.: Subcubic equivalences between path, matrix, and triangle problems. J. ACM 65(5) (2018)","DOI":"10.1145\/3186893"},{"key":"5_CR31","unstructured":"Wehar, M.: Unconditional time and space complexity lower bounds for intersection non-emptiness (2025). https:\/\/arxiv.org\/abs\/2512.00297"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-28404-4_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T23:21:06Z","timestamp":1780701666000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-28404-4_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032284037","9783032284044"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-28404-4_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"6 June 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"DLT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Developments in Language Theory","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Rouen","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 June 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 July 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"dlt2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/dlt-ncma-2026.sciencesconf.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}