{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,19]],"date-time":"2026-07-19T18:02:27Z","timestamp":1784484147384,"version":"3.55.0"},"publisher-location":"Cham","reference-count":32,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032313478","type":"print"},{"value":"9783032313485","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T00:00:00Z","timestamp":1784505600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T00:00:00Z","timestamp":1784505600000},"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":[[2027]]},"DOI":"10.1007\/978-3-032-31348-5_26","type":"book-chapter","created":{"date-parts":[[2026,7,19]],"date-time":"2026-07-19T17:30:01Z","timestamp":1784482201000},"page":"389-404","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Self-assembly of\u00a0Strings and\u00a0Languages Revisited: Efficient Membership Algorithms"],"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,7,20]]},"reference":[{"issue":"6","key":"26_CR1","doi-asserted-by":"publisher","first-page":"2527","DOI":"10.1137\/16M1061771","volume":"47","author":"A Abboud","year":"2018","unstructured":"Abboud, A., Backurs, A., Vassilevska Williams, V.: If the current clique algorithms are optimal, so is Valiant\u2019s parser. SIAM J. Comput. 47(6), 2527\u20132555 (2018)","journal-title":"SIAM J. Comput."},{"key":"26_CR2","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison-Wesley (1974)"},{"key":"26_CR3","doi-asserted-by":"crossref","unstructured":"Backurs, A., Indyk, P.: Which regular expression patterns are hard to match? In: FOCS, pp. 457\u2013466 (2016)","DOI":"10.1109\/FOCS.2016.56"},{"issue":"1","key":"26_CR4","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."},{"issue":"4","key":"26_CR5","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."},{"key":"26_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/10719839_9","volume-title":"LATIN 2000: Theoretical Informatics","author":"MA Bender","year":"2000","unstructured":"Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Gonnet, G.H., Viola, A. (eds.) LATIN 2000. LNCS, vol. 1776, pp. 88\u201394. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/10719839_9"},{"issue":"4","key":"26_CR7","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."},{"key":"26_CR8","doi-asserted-by":"crossref","unstructured":"Bringmann, K., Gr\u00f8nlund, A., K\u00fcnnemann, M., Larsen, K.G.: The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds. TheoretiCS 3 (2024)","DOI":"10.46298\/theoretics.24.22"},{"issue":"8","key":"26_CR9","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."},{"key":"26_CR10","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1016\/j.tcs.2017.03.040","volume":"701","author":"DJ Cho","year":"2017","unstructured":"Cho, D.J., Han, Y.S., Ng, T., Salomaa, K.: Outfix-guided insertion. Theor. Comput. Sci. 701, 70\u201384 (2017)","journal-title":"Theor. Comput. Sci."},{"key":"26_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/978-3-319-94631-3_5","volume-title":"Descriptional Complexity of Formal Systems","author":"D-J Cho","year":"2018","unstructured":"Cho, D.-J., Han, Y.-S., Salomaa, K., Smith, T.J.: Site-directed insertion: decision problems, maximality and minimality. In: Konstantinidis, S., Pighizzini, G. (eds.) DCFS 2018. LNCS, vol. 10952, pp. 49\u201361. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-94631-3_5"},{"issue":"1\u20132","key":"26_CR12","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":"26_CR13","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":"26_CR14","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":"26_CR15","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":"26_CR16","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":"26_CR17","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":"26_CR18","doi-asserted-by":"crossref","unstructured":"Fredman, M.L., Willard, D.E.: BLASTING through the information theoretic barrier with FUSION TREES. In: STOC, pp. 1\u20137 (1990)","DOI":"10.1145\/100216.100217"},{"key":"26_CR19","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley (1979)"},{"issue":"1\u20132","key":"26_CR20","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":"11","key":"26_CR21","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1145\/368996.369025","volume":"5","author":"AB Kahn","year":"1962","unstructured":"Kahn, A.B.: Topological sorting of large networks. Commun. ACM 5(11), 558\u2013562 (1962)","journal-title":"Commun. ACM"},{"issue":"6","key":"26_CR22","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":"26_CR23","unstructured":"Lange, M., Lei\u00df, H.: To CNF or not to CNF? An efficient yet presentable version of the CYK algorithm. Informatica Didact 8 (2009)"},{"issue":"9","key":"26_CR24","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":"26_CR25","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":"26_CR26","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":"26_CR27","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":"26_CR28","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":"26_CR29","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."},{"issue":"2","key":"26_CR30","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/S0022-0000(75)80046-8","volume":"10","author":"LG Valiant","year":"1975","unstructured":"Valiant, L.G.: General context-free recognition in less than cubic time. J. Comput. Syst. Sci. 10(2), 308\u2013315 (1975)","journal-title":"J. Comput. Syst. Sci."},{"key":"26_CR31","doi-asserted-by":"crossref","unstructured":"Vassilevska Williams, V.: On some fine-grained questions in algorithms and complexity. In: ICM, pp. 3447\u20133487. World Scientific (2018)","DOI":"10.1142\/9789813272880_0188"},{"key":"26_CR32","doi-asserted-by":"crossref","unstructured":"Vassilevska Williams, V., Williams, R.: Subcubic equivalences between path, matrix and triangle problems. In: FOCS, pp. 645\u2013654 (2010)","DOI":"10.1109\/FOCS.2010.67"}],"container-title":["Lecture Notes in Computer Science","Timeless Machines: Computability Across Eras"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-31348-5_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,19]],"date-time":"2026-07-19T17:30:04Z","timestamp":1784482204000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-31348-5_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,20]]},"ISBN":["9783032313478","9783032313485"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-31348-5_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,7,20]]},"assertion":[{"value":"20 July 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CiE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Conference on Computability in Europe","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Trier","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","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":"27 July 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31 July 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cie2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}