{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:34:16Z","timestamp":1759638856667,"version":"3.37.3"},"reference-count":12,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2017,12,1]],"date-time":"2017-12-01T00:00:00Z","timestamp":1512086400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2017,12,1]],"date-time":"2017-12-01T00:00:00Z","timestamp":1512086400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","award":["NRF-2013-Global Ph.D. Fellowship Program","2017K2A9A2A08000270"],"award-info":[{"award-number":["NRF-2013-Global Ph.D. Fellowship Program","2017K2A9A2A08000270"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","award":["2015R1D1A1A01060097"],"award-info":[{"award-number":["2015R1D1A1A01060097"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001700","name":"Ministry of Education, Culture, Sports, Science, and Technology","doi-asserted-by":"publisher","award":["No. 6F36"],"award-info":[{"award-number":["No. 6F36"]}],"id":[{"id":"10.13039\/501100001700","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["No. 15H06212","16H05854"],"award-info":[{"award-number":["No. 15H06212","16H05854"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002573","name":"Yonsei University","doi-asserted-by":"publisher","award":["Yonsie University Future-leading Research Initiative of 2016"],"award-info":[{"award-number":["Yonsie University Future-leading Research Initiative of 2016"]}],"id":[{"id":"10.13039\/501100002573","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Nat Comput"],"published-print":{"date-parts":[[2018,3]]},"DOI":"10.1007\/s11047-017-9661-y","type":"journal-article","created":{"date-parts":[[2017,12,1]],"date-time":"2017-12-01T08:45:16Z","timestamp":1512117916000},"page":"67-79","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Nondeterministic seedless oritatami systems and hardness of testing their equivalence"],"prefix":"10.1007","volume":"17","author":[{"given":"Yo-Sub","family":"Han","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hwee","family":"Kim","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Makoto","family":"Ota","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shinnosuke","family":"Seki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,12,1]]},"reference":[{"issue":"4","key":"9661_CR1","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1137\/0206054","volume":"6","author":"A Borodin","year":"1977","unstructured":"Borodin A (1977) On relating time and space to size and depth. SIAM J Comput 6(4):733\u2013744","journal-title":"SIAM J Comput"},{"issue":"6105","key":"9661_CR2","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1126\/science.1225722","volume":"338","author":"KL Frieda","year":"2012","unstructured":"Frieda KL, Block SM (2012) Direct observations of cotranscriptional folding in an adenine riboswitch. Science 338(6105):397\u2013400","journal-title":"Science"},{"key":"9661_CR5","doi-asserted-by":"publisher","first-page":"799","DOI":"10.1126\/science.1253920","volume":"345","author":"C Geary","year":"2014","unstructured":"Geary C, Rothemund PWK, Andersen ES (2014) A single-stranded architecture for cotranscriptional folding of RNA nanostructures. Science 345:799\u2013804","journal-title":"Science"},{"key":"9661_CR3","unstructured":"Geary C, Meunier PE, Schabanel N, Seki S (2015) Efficient universal computation by greedy molecular folding. CoRR. \n                    arXiv:1508.00510"},{"key":"9661_CR4","unstructured":"Geary C, Meunier PE, Schabanel N, Seki S (2016) Programming biomolecules that fold greedily during transcription. In: Proceedings of the 41st international symposium on mathematical foundations of computer science, pp 43:1\u201343:14"},{"key":"9661_CR6","volume-title":"Algorithm design","author":"J Kleinberg","year":"2011","unstructured":"Kleinberg J, Tardos \u00c9 (2011) Algorithm design. Addison-Wesley, Reading"},{"key":"9661_CR7","doi-asserted-by":"publisher","first-page":"1461","DOI":"10.1261\/rna.037390.112","volume":"19","author":"D Lai","year":"2013","unstructured":"Lai D, Proctor JR, Meyer IM (2013) On the importance of cotranscriptional RNA structure formation. RNA 19:1461\u20131473","journal-title":"RNA"},{"issue":"3","key":"9661_CR8","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1023\/A:1025449224520","volume":"2","author":"MJ P\u00e9rez-Jim\u00e9nez","year":"2003","unstructured":"P\u00e9rez-Jim\u00e9nez MJ, Romero-Jim\u00e9nez A, Sancho-Caparrini F (2003) Complexity classes in models of cellular computing with membranes. Nat Comput 2(3):265\u2013285","journal-title":"Nat Comput"},{"issue":"5","key":"9661_CR9","doi-asserted-by":"publisher","first-page":"2053","DOI":"10.1006\/jmbi.1998.2436","volume":"285","author":"E Rivas","year":"1999","unstructured":"Rivas E, Eddy SR (1999) A dynamic programming algorithm for RNA structure prediction including pseudoknots. J Mol Biol 285(5):2053\u20132068","journal-title":"J Mol Biol"},{"key":"9661_CR10","doi-asserted-by":"publisher","first-page":"W605","DOI":"10.1093\/nar\/gki447","volume":"33","author":"A Xayaphoummine","year":"2005","unstructured":"Xayaphoummine A, Bucher T, Isambert H (2005) Kinefold web server for RNA\/DNA folding path and structure prediction including pseudoknots and knots. Nucleic Acids Res 33:W605\u2013W610","journal-title":"Nucleic Acids Res"},{"issue":"13","key":"9661_CR11","doi-asserted-by":"publisher","first-page":"3406","DOI":"10.1093\/nar\/gkg595","volume":"31","author":"M Zuker","year":"2003","unstructured":"Zuker M (2003) Mfold web server for nucleic acid folding and hybridization prediction. Nucleic Acids Res 31(13):3406\u20133415","journal-title":"Nucleic Acids Res"},{"issue":"1","key":"9661_CR12","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1093\/nar\/9.1.133","volume":"9","author":"M Zuker","year":"1981","unstructured":"Zuker M, Stiegler P (1981) Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information. Nucleic Acids Res 9(1):133\u2013148","journal-title":"Nucleic Acids Res"}],"container-title":["Natural Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11047-017-9661-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-017-9661-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-017-9661-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,14]],"date-time":"2020-05-14T00:21:55Z","timestamp":1589415715000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11047-017-9661-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,1]]},"references-count":12,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,3]]}},"alternative-id":["9661"],"URL":"https:\/\/doi.org\/10.1007\/s11047-017-9661-y","relation":{},"ISSN":["1567-7818","1572-9796"],"issn-type":[{"type":"print","value":"1567-7818"},{"type":"electronic","value":"1572-9796"}],"subject":[],"published":{"date-parts":[[2017,12,1]]},"assertion":[{"value":"1 December 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}