{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T11:09:29Z","timestamp":1740136169117,"version":"3.37.3"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,6,27]],"date-time":"2020-06-27T00:00:00Z","timestamp":1593216000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,6,27]],"date-time":"2020-06-27T00:00:00Z","timestamp":1593216000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100005802","name":"Autoritatea National\u0103 pentru Cercetare Stiintific\u0103","doi-asserted-by":"publisher","award":["POC P-37-257"],"award-info":[{"award-number":["POC P-37-257"]}],"id":[{"id":"10.13039\/501100005802","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100005156","name":"Alexander von Humboldt-Stiftung","doi-asserted-by":"publisher","award":["2017"],"award-info":[{"award-number":["2017"]}],"id":[{"id":"10.13039\/100005156","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Nat Comput"],"published-print":{"date-parts":[[2021,6]]},"DOI":"10.1007\/s11047-020-09797-0","type":"journal-article","created":{"date-parts":[[2020,6,27]],"date-time":"2020-06-27T18:03:33Z","timestamp":1593281013000},"page":"193-203","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Hairpin completions and reductions: semilinearity properties"],"prefix":"10.1007","volume":"20","author":[{"given":"Henning","family":"Bordihn","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1457-8933","authenticated-orcid":false,"given":"Victor","family":"Mitrana","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrei","family":"P\u0103un","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mihaela","family":"P\u0103un","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,6,27]]},"reference":[{"key":"9797_CR1","doi-asserted-by":"crossref","unstructured":"Blattner M, Latteux M (1981) Parikh-bounded languages. In: Proceedings of the 8th international colloquium on automata, languages and programming (ICALP). LNCS, vol 115, pp 316\u2013323","DOI":"10.1007\/3-540-10843-2_26"},{"key":"9797_CR2","doi-asserted-by":"crossref","unstructured":"Bordihn H, Mitrana V, P\u0103un A, P\u0103un M (2019) Further properties of self-assembly by hairpin formation. In: Proceedings of the 18th international conference on unconventional computation and natural computation (UCNC). LNCS, vol 11493, pp 37\u201351","DOI":"10.1007\/978-3-030-19311-9_5"},{"key":"9797_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:503\u2013524","journal-title":"Theory Comput Syst"},{"key":"9797_CR4","doi-asserted-by":"crossref","unstructured":"Castellanos J, Mitrana V (2001) Some remarks on hairpin and loop languages. In: Words, semigroups, and transductions - festschrift in honor of gabriel thierrin. World Scientific, Singapore, pp 47\u201358","DOI":"10.1142\/9789812810908_0004"},{"key":"9797_CR5","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1007\/s11047-013-9393-6","volume":"13","author":"H-L Chen","year":"2014","unstructured":"Chen H-L, Doty D, Soloveichik D (2014) Deterministic function computation with chemical reaction networks. Nat Comput 13:517\u2013534","journal-title":"Nat Comput"},{"key":"9797_CR6","unstructured":"Cheptea D, Martin-Vide C, Mitrana V (2006) A new operation on words suggested by DNA biochemistry: hairpin completion. In: Proceedings of transgressive computing, pp 216\u2013228"},{"key":"9797_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. Theoret Comput Sci 374:74\u201381","journal-title":"Theoret Comput Sci"},{"key":"9797_CR8","doi-asserted-by":"crossref","unstructured":"Deaton R, Murphy R, Garzon M, Franceschetti DR, Stevens SE (1998) Good encodings for DNA-based solutions to combinatorial problems. In: Proceedings of DNA-based computers II. DIMACS series, vol 44, pp 247\u2013258","DOI":"10.1090\/dimacs\/044\/20"},{"key":"9797_CR9","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/s11047-015-9538-x","volume":"16","author":"SK Enaganti","year":"2007","unstructured":"Enaganti SK, Ibarra OH, Kari L, Kopecki S (2007) On the overlap assembly of strings and languages. Nat Comput 16:175\u2013185","journal-title":"Nat Comput"},{"key":"9797_CR10","unstructured":"Garzon M, Deaton R, Neathery P, Murphy RC, Franceschetti DR, Stevens E (1997) On the encoding problem for DNA computing. In: Proceedings of the third DIMACS workshop on DNA-based computing, pp 230\u2013237"},{"key":"9797_CR11","unstructured":"Garzon M, Deaton Nino LF, Stevens SE Jr, Wittner M (1998) Genome encoding for DNA computing. In: Proceedings of the third genetic programming conference, pp 684\u2013690"},{"key":"9797_CR12","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/S0022-0000(71)80024-7","volume":"5","author":"S Ginsburg","year":"1971","unstructured":"Ginsburg S (1971) AFL with the semilinear property. J Comput Syst Sci 5:365\u2013396","journal-title":"J Comput Syst Sci"},{"key":"9797_CR13","doi-asserted-by":"publisher","first-page":"285","DOI":"10.2140\/pjm.1966.16.285","volume":"16","author":"S Ginsburg","year":"1966","unstructured":"Ginsburg S, Spanier EH, Henry E (1966) Semigroups, Presburger formulas, and languages. Pac J Math 16:285\u2013296","journal-title":"Pac J Math"},{"key":"9797_CR14","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/0012-365X(77)90103-0","volume":"19","author":"J Goldstine","year":"1977","unstructured":"Goldstine J (1977) A simplified proof of Parikh\u2019s theorem. Discrete Math 19:235\u2013239","journal-title":"Discrete Math"},{"key":"9797_CR15","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 (2011) Bounded hairpin completion. Inf Comput 209:471\u2013485","journal-title":"Inf Comput"},{"key":"9797_CR16","doi-asserted-by":"crossref","unstructured":"Kari L, Konstantinidis S, Sosik P, Thierrin G (2005) On hairpin-free words and languages. In: Proceedings of the developments in language theory. LNCS, vol 3572, pp 296\u2013307","DOI":"10.1007\/11505877_26"},{"key":"9797_CR17","doi-asserted-by":"crossref","unstructured":"Kopczy\u0144ski E, To AW (2010) Parikh images of grammars: complexity and applications. In: Proceedings of the 25th annual IEEE symposium on logic in computer science (LICS), pp 80\u201389","DOI":"10.1109\/LICS.2010.21"},{"key":"9797_CR18","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 the iterated hairpin completion. Theor Comput Sci 412:3629\u20133638","journal-title":"Theor Comput Sci"},{"key":"9797_CR19","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:2143\u20132152","journal-title":"Discrete Appl Math"},{"key":"9797_CR20","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 (2009b) Two complementary operations inspired by the DNA hairpin formation: completion and reduction. Theor Comput Sci 410:417\u2013425","journal-title":"Theor Comput Sci"},{"key":"9797_CR21","doi-asserted-by":"crossref","unstructured":"Manea F, Mitrana V, Sempere J (2009c) Some remarks on superposition based on Watson\u2013Crick-Like complementarity. In: Proceedings of the developments in language theory. LNCS, vol 5583, pp 372\u2013383","DOI":"10.1007\/978-3-642-02737-6_30"},{"key":"9797_CR22","doi-asserted-by":"publisher","first-page":"4162","DOI":"10.1016\/j.tcs.2010.06.014","volume":"411","author":"F Manea","year":"2010","unstructured":"Manea F (2010) A series of algorithmic results related to the iterated hairpin completion. Theor Comput Sci 411:4162\u20134178","journal-title":"Theor Comput Sci"},{"key":"9797_CR23","doi-asserted-by":"crossref","unstructured":"Manea F, Mercas R, Mitrana V (2012) Hairpin lengthening and shortening of regular languages. In: Languages alive. LNCS, vol 7300, pp 145\u2013159","DOI":"10.1007\/978-3-642-31644-9_10"},{"key":"9797_CR24","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 (2015) Hairpin lengthening: language theoretic and algorithmic results. J Logic Comput 25:987\u20131009","journal-title":"J Logic Comput"},{"key":"9797_CR25","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1016\/0022-0000(78)90021-1","volume":"16","author":"D Oppen","year":"1978","unstructured":"Oppen D (1978) A $$2^{2^{2^{pn}}}$$ upper bound on the complexity of presburger arithmetic. J Comput Syst Sci 16:323\u2013332","journal-title":"J Comput Syst Sci"},{"key":"9797_CR26","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1145\/321356.321364","volume":"13","author":"R Parikh","year":"1966","unstructured":"Parikh R (1966) On context-free languages. J ACM 13:570\u2013581","journal-title":"J ACM"},{"key":"9797_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 (2001) Hairpin languages. Int J Found Comput Sci 12:837\u2013847","journal-title":"Int J Found Comput Sci"},{"key":"9797_CR28","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-0160-6","volume-title":"Numerical semigroups","author":"JC Rosales","year":"2009","unstructured":"Rosales JC, Garc\u00eda-S\u00e1nchez PA (2009) Numerical semigroups. Springer, New York"},{"volume-title":"Handbook of formal languages","year":"1997","key":"9797_CR29","unstructured":"Rozenberg G, Salomaa A (eds) (1997) Handbook of formal languages, vol 3. Springer, Berlin"},{"key":"9797_CR30","doi-asserted-by":"publisher","first-page":"1223","DOI":"10.1126\/science.288.5469.1223","volume":"288","author":"K Sakamoto","year":"2000","unstructured":"Sakamoto K, Gouzu H, Komiya K, Kiga D, Yokoyama S, Yokomori T, Hagiya M (2000) Molecular computation by DNA hairpin formation. Science 288:1223\u20131226","journal-title":"Science"},{"key":"9797_CR31","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1142\/S0129054116400153","volume":"27","author":"K Shikishima-Tsuji","year":"2016","unstructured":"Shikishima-Tsuji K (2016) Regularity of iterative hairpin completions of crossing $$(2,2)$$-words. Int J Found Comput Sci 27:375\u2013390","journal-title":"Int J Found Comput Sci"},{"key":"9797_CR32","first-page":"191","volume":"44","author":"E Winfree","year":"1999","unstructured":"Winfree E, Yang X, Seeman NC (1999) Universal computation via self-assembly of DNA: some theory and experiments. DNA based computers II. DIMACS 44:191\u2013213","journal-title":"DIMACS"}],"container-title":["Natural Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-020-09797-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11047-020-09797-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-020-09797-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,26]],"date-time":"2021-06-26T23:31:31Z","timestamp":1624750291000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11047-020-09797-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,27]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["9797"],"URL":"https:\/\/doi.org\/10.1007\/s11047-020-09797-0","relation":{},"ISSN":["1567-7818","1572-9796"],"issn-type":[{"type":"print","value":"1567-7818"},{"type":"electronic","value":"1572-9796"}],"subject":[],"published":{"date-parts":[[2020,6,27]]},"assertion":[{"value":"27 June 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}