{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T10:32:18Z","timestamp":1740133938375,"version":"3.37.3"},"reference-count":13,"publisher":"World Scientific Pub Co Pte Ltd","issue":"05","funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["18K19779"],"award-info":[{"award-number":["18K19779"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["19K11815"],"award-info":[{"award-number":["19K11815"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["20H04141"],"award-info":[{"award-number":["20H04141"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["20K11672"],"award-info":[{"award-number":["20K11672"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","award":["2020R1F1A1072738"],"award-info":[{"award-number":["2020R1F1A1072738"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2021,8]]},"abstract":"<jats:p> Oritatami is a computational model of RNA cotranscriptional folding, in which an RNA transcript is folding upon itself while being synthesized from its template DNA. This model is known to be Turing universal. Under the restriction on its parameters delay and arity both being 1, however, any deterministically foldable conformation is known to be at most ten times as large as its initial conformation (seed), and hence, the model becomes weaker. In this paper, we shall improve the size upper bound from [Formula: see text] down to [Formula: see text] and also provide a system that can fold into a conformation of size [Formula: see text]. These tighter bounds result from a novel graph representation of deterministic oritatami folding pathways. We shall also study the case in which a transcript is trapped in a region closed by a seed and show that under this confinement, the upper bound is further improved to [Formula: see text]. <\/jats:p>","DOI":"10.1142\/s0129054121410082","type":"journal-article","created":{"date-parts":[[2021,4,26]],"date-time":"2021-04-26T07:46:01Z","timestamp":1619423161000},"page":"575-596","source":"Crossref","is-referenced-by-count":1,"title":["Linear Bounds on the Size of Conformations in Greedy Deterministic Oritatami"],"prefix":"10.1142","volume":"32","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5319-0395","authenticated-orcid":false,"given":"Szil\u00e1rd Zsolt","family":"Fazekas","sequence":"first","affiliation":[{"name":"Graduate School of Engineering Science, Akita University, 1-1, Tegata Gakuen-machi, Akita, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hwee","family":"Kim","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Incheon National University, 119 Academy-Ro, Yeonsu-Gu, Incheon 22012, Republic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ryuichi","family":"Matsuoka","sequence":"additional","affiliation":[{"name":"Department of Computer and Network Engineering, The University of Electro-Communications, 1-5-1, Chofugaoka, Chofu, Tokyo, 1828585, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4478-4196","authenticated-orcid":false,"given":"Reoto","family":"Morita","sequence":"additional","affiliation":[{"name":"Department of Computer and Network Engineering, The University of Electro-Communications, 1-5-1, Chofugaoka, Chofu, Tokyo, 1828585, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0276-3322","authenticated-orcid":false,"given":"Shinnosuke","family":"Seki","sequence":"additional","affiliation":[{"name":"Department of Computer and Network Engineering, The University of Electro-Communications, 1-5-1, Chofugaoka, Chofu, Tokyo, 1828585, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2021,4,23]]},"reference":[{"key":"S0129054121410082BIB001","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380881"},{"issue":"1","key":"S0129054121410082BIB002","first-page":"1","volume":"15","author":"Cook M.","year":"2004","journal-title":"Compl. Syst."},{"key":"S0129054121410082BIB003","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-00030-1_2"},{"key":"S0129054121410082BIB004","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.08.023"},{"volume-title":"Feynman Lectures on Computation","year":"1996","author":"Feynman R. P.","key":"S0129054121410082BIB005"},{"key":"S0129054121410082BIB006","series-title":"LIPIcs","first-page":"23:1","volume-title":"ISAAC 2018: Proc. 29th Int. Symp. Algorithms and Computation","volume":"123","author":"Geary C.","year":"2018"},{"key":"S0129054121410082BIB007","doi-asserted-by":"publisher","DOI":"10.1126\/science.1253920"},{"key":"S0129054121410082BIB008","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055446"},{"key":"S0129054121410082BIB009","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03409-1_24"},{"key":"S0129054121410082BIB010","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-27660-6_32"},{"volume-title":"LATIN2020: Proc. 14th Latin American Symposium on Theoretical Informatics","series-title":"LNCS","author":"Pchelina D.","key":"S0129054121410082BIB011"},{"key":"S0129054121410082BIB012","first-page":"459","volume-title":"STOC 2000: Proc. 32nd Ann. ACM Symp. Theory of Computing","author":"Rothemund P. W. K.","year":"2000"},{"key":"S0129054121410082BIB013","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2006.12.008"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054121410082","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,12]],"date-time":"2021-08-12T01:44:47Z","timestamp":1628732687000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054121410082"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,23]]},"references-count":13,"journal-issue":{"issue":"05","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["10.1142\/S0129054121410082"],"URL":"https:\/\/doi.org\/10.1142\/s0129054121410082","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2021,4,23]]}}}