{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T06:13:54Z","timestamp":1784528034870,"version":"3.55.0"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,1,23]],"date-time":"2016-01-23T00:00:00Z","timestamp":1453507200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,1,23]],"date-time":"2016-01-23T00:00:00Z","timestamp":1453507200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1117708"],"award-info":[{"award-number":["CCF-1117708"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002790","name":"Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["R2824A01"],"award-info":[{"award-number":["R2824A01"]}],"id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"publisher"}]},{"name":"University of Western Ontario"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Nat Comput"],"published-print":{"date-parts":[[2017,3]]},"DOI":"10.1007\/s11047-015-9538-x","type":"journal-article","created":{"date-parts":[[2016,1,23]],"date-time":"2016-01-23T06:32:32Z","timestamp":1453530752000},"page":"175-185","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["On the overlap assembly of strings and languages"],"prefix":"10.1007","volume":"16","author":[{"given":"Srujan Kumar","family":"Enaganti","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Oscar H.","family":"Ibarra","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lila","family":"Kari","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Steffen","family":"Kopecki","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,1,23]]},"reference":[{"key":"9538_CR1","doi-asserted-by":"crossref","unstructured":"Alur R, Madhusudan P (2004) Visibly pushdown languages. In: Proceedings of ACM symposium on theory of computing, STOC. ACM-Press, pp 202\u2013211","DOI":"10.1145\/1007352.1007390"},{"issue":"4","key":"9538_CR2","doi-asserted-by":"publisher","first-page":"706","DOI":"10.1016\/j.jtbi.2007.06.007","volume":"248","author":"A Angeleska","year":"2007","unstructured":"Angeleska A, Jonoska N, Saito M, Landweber LF (2007) RNA-guided DNA assembly. J Theor Biol 248(4):706\u2013720","journal-title":"J Theor Biol"},{"issue":"4","key":"9538_CR3","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 (2006) Superposition based on Watson\u2013Crick-like complementarity. Theory Comput Syst 39(4):503\u2013524","journal-title":"Theory Comput Syst"},{"issue":"5567","key":"9538_CR4","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1126\/science.1069528","volume":"296","author":"RS Braich","year":"2002","unstructured":"Braich RS, Chelyapov N, Johnson C, Rothemund PWK, Adleman L (2002) Solution of a 20-variable 3-SAT problem on a DNA computer. Science 296(5567):499\u2013502","journal-title":"Science"},{"key":"9538_CR5","unstructured":"Cheptea D, Mart\u00edn-Vide C, Mitrana V (2006) A new operation on words suggested by DNA biochemistry: hairpin completion. In: Proceedings of transgressive computing, TC, pp 216\u2013228"},{"key":"9538_CR6","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/j.tcs.2012.04.002","volume":"454","author":"E Chiniforooshan","year":"2012","unstructured":"Chiniforooshan E, Daley M, Ibarra OH, Kari L, Seki S (2012) One-reversal counter machines and multihead automata: revisited. Theor Comput Sci 454:81\u201387","journal-title":"Theor Comput Sci"},{"issue":"1\u20133","key":"9538_CR7","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 (2007) Self-assembly of strings and languages. Theor Comput Sci 374(1\u20133):74\u201381","journal-title":"Theor Comput Sci"},{"issue":"1\u20133","key":"9538_CR8","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/S0303-2647(99)00030-1","volume":"52","author":"AR Cukras","year":"1999","unstructured":"Cukras AR, Faulhammer D, Lipton RJ, Landweber LF (1999) Chess games: a model for RNA based computation. Biosystems 52(1\u20133):35\u201345","journal-title":"Biosystems"},{"key":"9538_CR9","doi-asserted-by":"crossref","unstructured":"Daley M, Kari L, Gloor G, Siromoney R: Circular contextual insertions\/deletions with applications to biomolecular computation. In: Proceedings of string processing and information retrieval, SPIRE, pp 47\u201354 (1999)","DOI":"10.1109\/SPIRE.1999.796577"},{"issue":"4","key":"9538_CR10","first-page":"353","volume":"44","author":"J Dassow","year":"2000","unstructured":"Dassow J, Mart\u00edn-Vide C, P\u0103un G, Rodr\u00edguez-Pat\u00f3n A (2000) Conditional concatenation. Fundam Inf 44(4):353\u2013372","journal-title":"Fundam Inf"},{"key":"9538_CR11","doi-asserted-by":"publisher","DOI":"10.1142\/9789812810908_0007","volume-title":"Circularity and other invariants of gene assembly in ciliates","author":"A Ehrenfeucht","year":"2001","unstructured":"Ehrenfeucht A, Petre I, Prescott DM, Rozenberg G (2001) Circularity and other invariants of gene assembly in ciliates. World Scientific, Singapore"},{"key":"9538_CR12","doi-asserted-by":"crossref","first-page":"179","DOI":"10.3233\/FI-2015-1206","volume":"138","author":"SK Enaganti","year":"2015","unstructured":"Enaganti SK, Kari L, Kopecki S (2015) A formal language model of DNA polymerase activity. Fundam Inform 138:179\u2013192","journal-title":"Fundam Inform"},{"issue":"4","key":"9538_CR13","doi-asserted-by":"publisher","first-page":"1385","DOI":"10.1073\/pnas.97.4.1385","volume":"97","author":"D Faulhammer","year":"2000","unstructured":"Faulhammer D, Cukras AR, Lipton RJ, Landweber LF (2000) Molecular computation: RNA solutions to chess problems. Proc Natl Acad Sci 97(4):1385\u20131389","journal-title":"Proc Natl Acad Sci"},{"key":"9538_CR14","doi-asserted-by":"crossref","unstructured":"Franco G (2005) A polymerase based algorithm for SAT. In: Coppo M, Lodi E, Pinna G (eds) Theoretical computer science, Lecture notes in computer science, vol 3701. Springer, Berlin, pp 237\u2013250","DOI":"10.1007\/11560586_20"},{"issue":"2","key":"9538_CR16","doi-asserted-by":"publisher","first-page":"805","DOI":"10.1007\/s11047-010-9199-8","volume":"10","author":"G Franco","year":"2011","unstructured":"Franco G, Manca V (2011) Algorithmic applications of XPCR. Nat Comput 10(2):805\u2013819","journal-title":"Nat Comput"},{"key":"9538_CR15","doi-asserted-by":"crossref","unstructured":"Franco G, Giagulli C, Laudanna C, Manca V (2005) DNA extraction by XPCR. In: Ferretti C, Mauri G, Zandron C (eds) Proceedings of DNA computing (DNA 11), LNCS, vol 3384, pp 104\u2013112","DOI":"10.1007\/11493785_9"},{"key":"9538_CR17","doi-asserted-by":"crossref","unstructured":"Franco G, Manca V, Giagulli C, Laudanna C (2006) DNA recombination by XPCR. In: Carbone A, Pierce NA (eds) Proceedings of DNA computing (DNA 12), LNCS, vol 3892, pp 55\u201366","DOI":"10.1007\/11753681_5"},{"issue":"1\u20132","key":"9538_CR18","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1080\/00207168908803788","volume":"31","author":"RW Gatterdam","year":"1989","unstructured":"Gatterdam RW (1989) Splicing systems and regularity. Int J Comput Math 31(1\u20132):63\u201367","journal-title":"Int J Comput Math"},{"key":"9538_CR19","unstructured":"Head T, Pixton D, Goode E (2003) Splicing systems: regularity and below. In: Hagiya M, Ohuchi A (eds) DNA based computers: DNA computing, DNA 8. LNCS, vol 2568, pp 262\u2013268"},{"key":"9538_CR20","volume-title":"Introduction to automata theory, languages, and computation","author":"JE Hopcroft","year":"1978","unstructured":"Hopcroft JE, Ullman JD (1978) Introduction to automata theory, languages, and computation. Addison-Wesley, Reading"},{"issue":"1","key":"9538_CR21","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1145\/322047.322058","volume":"25","author":"OH Ibarra","year":"1978","unstructured":"Ibarra OH (1978) Reversal-bounded multicounter machines and their decision problems. J ACM 25(1):116\u2013133","journal-title":"J ACM"},{"key":"9538_CR22","doi-asserted-by":"crossref","unstructured":"Ibarra OH (2014) Automata with reversal-bounded counters: a survey. In: Proceedings of descriptional complexity of formal systems, DCFS. Springer, pp 5\u201322","DOI":"10.1007\/978-3-319-09704-6_2"},{"issue":"06","key":"9538_CR23","doi-asserted-by":"publisher","first-page":"1291","DOI":"10.1142\/S0129054112400539","volume":"23","author":"OH Ibarra","year":"2012","unstructured":"Ibarra OH, Seki S (2012) Characterizations of bounded semilinear languages by one-way and two-way deterministic machines. Int J Found Comput Sci 23(06):1291\u20131305","journal-title":"Int J Found Comput Sci"},{"key":"9538_CR24","doi-asserted-by":"crossref","unstructured":"J\u00fcrgensen H, Konstantinidis S (1997) Codes. In: Handbook of formal languages. Springer, Berlin, pp 511\u2013607","DOI":"10.1007\/978-3-642-59136-5_8"},{"issue":"3","key":"9538_CR25","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1006\/jtbi.1997.0475","volume":"188","author":"PD Kaplan","year":"1997","unstructured":"Kaplan PD, Ouyang Q, Thaler DS, Libchaber A (1997) Parallel overlap assembly for the construction of computational DNA libraries. J Theor Biol 188(3):333\u2013341","journal-title":"J Theor Biol"},{"issue":"1\u20132","key":"9538_CR28","first-page":"165","volume":"73","author":"L Kari","year":"2006","unstructured":"Kari L, Losseva E (2006) Block substitutions and their properties. Fundam Inform 73(1\u20132):165\u2013178","journal-title":"Fundam Inform"},{"issue":"1\u20133","key":"9538_CR30","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1016\/j.tcs.2008.01.037","volume":"396","author":"L Kari","year":"2008","unstructured":"Kari L, Sos\u00edk P (2008) On the weight of universal insertion grammars. Theor Comput Sci 396(1\u20133):264\u2013270","journal-title":"Theor Comput Sci"},{"key":"9538_CR27","unstructured":"Kari L, Kopecki S (2012) Deciding whether a regular language is generated by a splicing system. In: Stefanovic D, Turberfield A (eds) DNA computing and molecular programming (DNA 18). LNCS, vol 7433, pp 98\u2013109"},{"key":"9538_CR26","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/978-3-642-60207-8_31","volume-title":"Jewels are forever","author":"L Kari","year":"1999","unstructured":"Kari L, Kari J, Landweber L (1999a) Reversible molecular computation in ciliates. In: Karhum\u00e4ki J, Maurer H, P\u0103un G, Rozenberg G (eds) Jewels are forever. Springer, Berlin, pp 353\u2013363"},{"key":"9538_CR29","doi-asserted-by":"crossref","unstructured":"Kari L, P\u0103un G, Thierrin G, Yu S (1999b) At the crossroads of DNA computing and formal languages: characterizing recursively enumerable languages using insertion\u2013deletion systems. In: DNA based computers III (DNA3), DIMACS, vol\u00a048, pp 329\u2013347","DOI":"10.1090\/dimacs\/048\/23"},{"key":"9538_CR31","unstructured":"Kim SM (1997) An algorithm for identifying spliced languages. In: Jiang T, Lee D (eds) Proceedings of computing and combinatorics conference, COCOON. LNCS, vol 1276, pp 403\u2013411"},{"issue":"29","key":"9538_CR32","doi-asserted-by":"publisher","first-page":"3629","DOI":"10.1016\/j.tcs.2011.03.009","volume":"412","author":"S Kopecki","year":"2011","unstructured":"Kopecki S (2011) On iterated hairpin completion. Theor Comput Sci 412(29):3629\u20133638","journal-title":"Theor Comput Sci"},{"issue":"1\u20133","key":"9538_CR33","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0303-2647(99)00027-1","volume":"52","author":"LF Landweber","year":"1999","unstructured":"Landweber LF, Kari L (1999) The evolution of cellular computing: natures solution to a computational problem. Biosystems 52(1\u20133):3\u201313","journal-title":"Biosystems"},{"issue":"9","key":"9538_CR34","doi-asserted-by":"publisher","first-page":"679","DOI":"10.1007\/s00500-004-0398-z","volume":"9","author":"L Ledesma","year":"2005","unstructured":"Ledesma L, Manrique D, Rodr\u00edguez-Pat\u00f3n A (2005) A tissue P system and a DNA microfluidic device for solving the shortest common superstring problem. Soft Comput 9(9):679\u2013685","journal-title":"Soft Comput"},{"issue":"2","key":"9538_CR35","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1016\/j.mbs.2007.08.010","volume":"211","author":"V Manca","year":"2008","unstructured":"Manca V, Franco G (2008) Computing by polymerase chain reaction. Math Biosci 211(2):282\u2013298","journal-title":"Math Biosci"},{"key":"9538_CR37","unstructured":"Manea F, Mitrana V (2007) Hairpin completion versus hairpin reduction. In: Cooper SB, L\u00f6we B, Sorbi A (eds) Proceedings of computability in Europe, CiE. LNCS, vol 4497, pp 532\u2013541"},{"issue":"9","key":"9538_CR36","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 (2009a) On some algorithmic problems regarding the hairpin completion. Discrete Appl Math 157(9):2143\u20132152","journal-title":"Discrete Appl Math"},{"key":"9538_CR38","doi-asserted-by":"crossref","unstructured":"Manea F, Mitrana V, Sempere J (2009b) Some remarks on superposition based on Watson\u2013Crick\u2013like complementarity. In: Diekert V, Nowotka D (eds) Developments in language theory. LNCS, vol 5583, pp 372\u2013383","DOI":"10.1007\/978-3-642-02737-6_30"},{"issue":"2","key":"9538_CR39","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/S0304-3975(02)00659-X","volume":"296","author":"C Mart\u00edn-Vide","year":"2003","unstructured":"Mart\u00edn-Vide C, P\u0103un G, Pazos J, Rodr\u00edguez-Pat\u00f3n A (2003) Tissue P systems. Theor Comput Sci 296(2):295\u2013326","journal-title":"Theor Comput Sci"},{"key":"9538_CR40","doi-asserted-by":"crossref","unstructured":"Mehlhorn K (1980) Pebbling moutain ranges and its application of DCFL-recognition. In: Proceedings of automata, languages and programming, ICALP, pp 422\u2013435. Springer","DOI":"10.1007\/3-540-10003-2_89"},{"issue":"3","key":"9538_CR41","doi-asserted-by":"publisher","first-page":"437","DOI":"10.2307\/1970290","volume":"74","author":"ML Minsky","year":"1961","unstructured":"Minsky ML (1961) Recursive unsolvability of post\u2019s problem of \u201ctag\u201d and other topics in theory of turing machines. Ann Math 74(3):437\u2013455","journal-title":"Ann Math"},{"issue":"5337","key":"9538_CR42","doi-asserted-by":"publisher","first-page":"446","DOI":"10.1126\/science.278.5337.446","volume":"278","author":"Q Ouyang","year":"1997","unstructured":"Ouyang Q, Kaplan PD, Liu S, Libchaber A (1997) DNA solution of the maximal clique problem. Science 278(5337):446\u2013449","journal-title":"Science"},{"key":"9538_CR46","volume-title":"DNA computing: new computing paradigms","author":"G P\u0103un","year":"2006","unstructured":"P\u0103un G, Rozenberg G, Salomaa A (2006) DNA computing: new computing paradigms. Springer, New York"},{"issue":"4","key":"9538_CR45","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1142\/S0129054108006005","volume":"19","author":"G P\u0103un","year":"2008","unstructured":"P\u0103un G, P\u00e8rez-Jim\u00e8nez MJ, Yokomori T (2008) Representations and characterizations of languages in Chomsky hierarchy by means of insertion\u2013deletion systems. Int J Found Comput Sci 19(4):859\u2013871","journal-title":"Int J Found Comput Sci"},{"issue":"1\u20132","key":"9538_CR43","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/0166-218X(95)00079-7","volume":"69","author":"D Pixton","year":"1996","unstructured":"Pixton D (1996) Regularity of splicing languages. Discrete Appl Math 69(1\u20132):101\u2013124","journal-title":"Discrete Appl Math"},{"issue":"3","key":"9538_CR44","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1078\/0932-4739-00807","volume":"37","author":"DM Prescott","year":"2001","unstructured":"Prescott DM, Ehrenfeucht A, Rozenberg G (2001) Molecular operations for DNA processing in hypotrichous ciliates. Eur J Protistol 37(3):241\u2013260","journal-title":"Eur J Protistol"},{"issue":"22","key":"9538_CR47","doi-asserted-by":"publisher","first-page":"10747","DOI":"10.1073\/pnas.91.22.10747","volume":"91","author":"WP Stemmer","year":"1994","unstructured":"Stemmer WP (1994) DNA shuffling by random fragmentation and reassembly: in vitro recombination for molecular evolution. Proc Natl Acad Sci 91(22):10747\u201310751","journal-title":"Proc Natl Acad Sci"},{"issue":"4","key":"9538_CR48","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1023\/B:NACO.0000006769.27984.23","volume":"2","author":"A Takahara","year":"2003","unstructured":"Takahara A, Yokomori T (2003) On the computational power of insertion\u2013deletion systems. Nat Comput 2(4):321\u2013336","journal-title":"Nat Comput"},{"issue":"10","key":"9538_CR49","doi-asserted-by":"crossref","first-page":"1021","DOI":"10.1631\/jzus.2005.A1021","volume":"6","author":"M Yong","year":"2005","unstructured":"Yong M, Xiao-Gang J, Xian-Chuang S, Bo P (2005) Minimizing of the only-insertion insdel systems. J Zhejiang Univ Sci A 6(10):1021\u20131025","journal-title":"J Zhejiang Univ Sci A"}],"container-title":["Natural Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-015-9538-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11047-015-9538-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-015-9538-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-015-9538-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T06:36:02Z","timestamp":1748759762000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11047-015-9538-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1,23]]},"references-count":49,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,3]]}},"alternative-id":["9538"],"URL":"https:\/\/doi.org\/10.1007\/s11047-015-9538-x","relation":{},"ISSN":["1567-7818","1572-9796"],"issn-type":[{"value":"1567-7818","type":"print"},{"value":"1572-9796","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,1,23]]},"assertion":[{"value":"23 January 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}