{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:24:49Z","timestamp":1759638289047,"version":"3.37.3"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,11,17]],"date-time":"2021-11-17T00:00:00Z","timestamp":1637107200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2021,11,17]],"date-time":"2021-11-17T00:00:00Z","timestamp":1637107200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1817602"],"award-info":[{"award-number":["CCF-1817602"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Nat Comput"],"published-print":{"date-parts":[[2024,6]]},"DOI":"10.1007\/s11047-021-09875-x","type":"journal-article","created":{"date-parts":[[2021,11,17]],"date-time":"2021-11-17T06:03:41Z","timestamp":1637129021000},"page":"387-405","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Verification and computation in restricted Tile Automata"],"prefix":"10.1007","volume":"23","author":[{"given":"David","family":"Caballero","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5423-7615","authenticated-orcid":false,"given":"Timothy","family":"Gomez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert","family":"Schweller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tim","family":"Wylie","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,11,17]]},"reference":[{"key":"9875_CR1","doi-asserted-by":"crossref","unstructured":"Adleman LM, Cheng Q, Goel A, Huang MDA, Kempe D, de\u00a0Espan\u00e9s PM, Rothemund PWK (2002) Combinatorial optimization problems in self-assembly. In: Proceedings of the 34th annual ACM symposium on theory of computing, pp 23\u201332","DOI":"10.1145\/509907.509913"},{"key":"9875_CR2","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1007\/978-3-030-26807-7_8","volume-title":"DNA computing and molecular programming","author":"JC Alumbaugh","year":"2019","unstructured":"Alumbaugh JC, Daymude JJ, Demaine ED, Patitz MJ, Richa AW (2019) Simulation of programmable matter systems using active tile-based self-assembly. In: Thachuk C, Liu Y (eds) DNA computing and molecular programming. Springer, Cham, pp 140\u2013158"},{"key":"9875_CR3","doi-asserted-by":"publisher","unstructured":"Caballero D, Gomez T, Schweller R, Wylie T (2020) Verification and Computation in Restricted Tile Automata. In: Geary C, Patitz MJ (eds) 26th international conference on DNA computing and molecular programming (DNA 26), Leibniz International Proceedings in Informatics (LIPIcs), vol. 174, pp. 10:1\u201310:18. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany. https:\/\/doi.org\/10.4230\/LIPIcs.DNA.2020.10. URL https:\/\/drops.dagstuhl.de\/opus\/volltexte\/2020\/12963","DOI":"10.4230\/LIPIcs.DNA.2020.10"},{"key":"9875_CR4","unstructured":"Caballero D, Gomez T, Schweller R, Wylie T (2021) Covert computation in staged self-assembly: Verification is pspace-complete. In: Proceedings of the 29th European Symposium on Algorithms, ESA\u201921"},{"key":"9875_CR5","unstructured":"Cannon S, Demaine ED, Demaine ML, Eisenstat S, Patitz MJ, Schweller RT, Summers SM, Winslow A (2013) Two Hands Are Better Than One (up to constant factors): Self-Assembly In The 2HAM vs. aTAM. In: 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a020, pp. 172\u2013184. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik"},{"key":"9875_CR6","doi-asserted-by":"publisher","unstructured":"Cantu AA, Luchsinger A, Schweller R, Wylie T (2020) Covert Computation in Self-Assembled Circuits. Algorithmica. https:\/\/doi.org\/10.1007\/s00453-020-00764-w. arXiv:1908.06068","DOI":"10.1007\/s00453-020-00764-w"},{"key":"9875_CR7","doi-asserted-by":"publisher","unstructured":"Cantu AA, Luchsinger A, Schweller R, Wylie T (2020) Signal Passing Self-Assembly Simulates Tile Automata. In: Y.\u00a0Cao, S.W. Cheng, M.\u00a0Li (eds.) 31st International Symposium on Algorithms and Computation (ISAAC 2020), Leibniz International Proceedings in Informatics (LIPIcs), vol. 181, pp. 53:1\u201353:17. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany. https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2020.53. URL https:\/\/drops.dagstuhl.de\/opus\/volltexte\/2020\/13397","DOI":"10.4230\/LIPIcs.ISAAC.2020.53"},{"key":"9875_CR8","doi-asserted-by":"crossref","unstructured":"Chalk C, Luchsinger A, Martinez E, Schweller R, Winslow A, Wylie T (2018) Freezing simulates non-freezing tile automata. In: International Conference on DNA Computing and Molecular Programming, pp. 155\u2013172. Springer","DOI":"10.1007\/978-3-030-00030-1_10"},{"key":"9875_CR9","unstructured":"Chalk C, Luchsinger A, Schweller R, Wylie T (2018) Self-assembly of any shape with constant tile types using high temperature. In: Proceedings of the 26th Annual European Symposium on Algorithms, ESA\u201918"},{"issue":"1","key":"9875_CR10","first-page":"1","volume":"15","author":"M Cook","year":"2004","unstructured":"Cook M (2004) Universality in elementary cellular automata. Complex Syst 15(1):1\u201340","journal-title":"Complex Syst"},{"key":"9875_CR11","doi-asserted-by":"crossref","unstructured":"Daymude JJ, Hinnenthal K, Richa AW, Scheideler C (2019) Computing by programmable particles. In: Distributed computing by mobile entities: current research in moving and computing, pp 615\u2013681. Springer, Cham","DOI":"10.1007\/978-3-030-11072-7_22"},{"issue":"3","key":"9875_CR12","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/s11047-008-9073-0","volume":"7","author":"ED Demaine","year":"2008","unstructured":"Demaine ED, Demaine ML, Fekete SP, Ishaque M, Rafalin E, Schweller RT, Souvaine DL (2008) Staged self-assembly: nanomanufacture of arbitrary shapes with o (1) glues. Natural Comput 7(3):347\u2013370","journal-title":"Natural Comput"},{"key":"9875_CR13","doi-asserted-by":"crossref","unstructured":"Demaine ED, Eisenstat S, Ishaque M, Winslow A (2011) One-dimensional staged self-assembly. In: Proceedings of the 17th international conference on DNA computing and molecular programming, DNA\u201911, pp. 100\u2013114","DOI":"10.1007\/978-3-642-23638-9_10"},{"issue":"1","key":"9875_CR14","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/s00453-012-9631-9","volume":"66","author":"D Doty","year":"2013","unstructured":"Doty D, Kari L, Masson B (2013) Negative interactions in irreversible self-assembly. Algorithmica 66(1):153\u2013172","journal-title":"Algorithmica"},{"key":"9875_CR15","unstructured":"Evans C (2014) Crystals that count! physical principles and experimental investigations of dna tile self-assembly. Ph.D. thesis, California Inst. of Tech"},{"issue":"1\u20132","key":"9875_CR16","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.tcs.2010.10.005","volume":"412","author":"E Goles","year":"2011","unstructured":"Goles E, Meunier PE, Rapaport I, Theyssier G (2011) Communication complexity and intrinsic universality in cellular automata. Theor Comput Sci 412(1\u20132):2\u201321","journal-title":"Theor Comput Sci"},{"issue":"2","key":"9875_CR17","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1002\/anie.200390075","volume":"42","author":"AG Kanaras","year":"2003","unstructured":"Kanaras AG, Wang Z, Bates AD, Cosstick R, Brust M (2003) Towards multistep nanostructure synthesis: programmed enzymatic self-assembly of DNA\/gold systems. Angewandte Chemie International Edition 42(2):191\u2013194","journal-title":"Angewandte Chemie International Edition"},{"issue":"4","key":"9875_CR18","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1002\/cphc.201700982","volume":"19","author":"R Kawano","year":"2018","unstructured":"Kawano R (2018) Synthetic ion channels and DNA logic gates as components of molecular robots. ChemPhysChem 19(4):359\u2013366. https:\/\/doi.org\/10.1002\/cphc.201700982","journal-title":"ChemPhysChem"},{"issue":"1","key":"9875_CR19","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s11047-015-9512-7","volume":"15","author":"A Keenan","year":"2016","unstructured":"Keenan A, Schweller R, Sherman M, Zhong X (2016) Fast arithmetic in algorithmic self-assembly. Natural Comput 15(1):115\u2013128","journal-title":"Natural Comput"},{"key":"9875_CR20","doi-asserted-by":"publisher","DOI":"10.1016\/j.jconrel.2019.04.028","author":"C Kimna","year":"2019","unstructured":"Kimna C, Lieleg O (2019) Engineering an orchestrated release avalanche from hydrogels using DNA-nanotechnology. J Controll Release. https:\/\/doi.org\/10.1016\/j.jconrel.2019.04.028","journal-title":"J Controll Release"},{"key":"9875_CR21","doi-asserted-by":"publisher","unstructured":"Kuroda SY (1964) Classes of languages and linear-bounded automata. Information and Control 7(2):207\u2013223. https:\/\/doi.org\/10.1016\/S0019-9958(64)90120-2. URL http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0019995864901202","DOI":"10.1016\/S0019-9958(64)90120-2"},{"key":"9875_CR22","doi-asserted-by":"publisher","DOI":"10.1007\/s11047-018-9707-9","author":"A Luchsinger","year":"2018","unstructured":"Luchsinger A, Schweller R, Wylie T (2018) Self-assembly of shapes at constant scale using repulsive forces. Natural Comput. https:\/\/doi.org\/10.1007\/s11047-018-9707-9","journal-title":"Natural Comput"},{"key":"9875_CR23","doi-asserted-by":"crossref","unstructured":"Padilla JE, Patitz MJ, Pena R, Schweller RT, Seeman NC, Sheline R, Summers SM, Zhong X (2013) Asynchronous signal passing for tile self-assembly: Fuel efficient computation and efficient assembly of shapes. In: Unconventional Computation and Natural Computation, pp. 174\u2013185. Springer","DOI":"10.1007\/978-3-642-39074-6_17"},{"key":"9875_CR24","doi-asserted-by":"crossref","unstructured":"Schweller R, Sherman M (2013) Fuel efficient computation in passive self-assembly. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA\u201913, pp. 1513\u20131525. SIAM","DOI":"10.1137\/1.9781611973105.109"},{"key":"9875_CR25","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1007\/978-3-319-66799-7_7","volume-title":"DNA computing and molecular programming","author":"R Schweller","year":"2017","unstructured":"Schweller R, Winslow A, Wylie T (2017) Complexities for high-temperature two-handed tile self-assembly. In: Brijder R, Qian L (eds) DNA computing and molecular programming. Springer, Cham, pp 98\u2013109"},{"issue":"8","key":"9875_CR26","doi-asserted-by":"publisher","first-page":"3114","DOI":"10.1007\/s00453-019-00573-w","volume":"81","author":"R Schweller","year":"2019","unstructured":"Schweller R, Winslow A, Wylie T (2019) Nearly constant tile complexity for any shape in two-handed tile assembly. Algorithmica 81(8):3114\u20133135","journal-title":"Algorithmica"},{"issue":"1","key":"9875_CR27","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/s11047-018-9701-2","volume":"18","author":"R Schweller","year":"2019","unstructured":"Schweller R, Winslow A, Wylie T (2019) Verification in staged tile self-assembly. Natural Comput 18(1):107\u2013117","journal-title":"Natural Comput"},{"key":"9875_CR28","unstructured":"Spakowski H (2006) Completeness for parallel access to np and counting class separation. Ausgezeichnete Informatikdissertationen 2005"},{"key":"9875_CR29","unstructured":"Winfree E (1998) Algorithmic self-assembly of DNA. Ph.D. thesis, California Institute of Technology"},{"issue":"2","key":"9875_CR30","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s11047-014-9423-z","volume":"14","author":"A Winslow","year":"2015","unstructured":"Winslow A (2015) Staged self-assembly and polyomino context-free grammars. Natural Comput 14(2):293\u2013302","journal-title":"Natural Comput"},{"issue":"4","key":"9875_CR31","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1007\/s11047-013-9388-3","volume":"12","author":"T Worsch","year":"2013","unstructured":"Worsch T (2013) Towards intrinsically universal asynchronous ca. Natural Comput 12(4):539\u2013550","journal-title":"Natural Comput"}],"container-title":["Natural Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-021-09875-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11047-021-09875-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-021-09875-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,2]],"date-time":"2024-08-02T19:05:01Z","timestamp":1722625501000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11047-021-09875-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,17]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["9875"],"URL":"https:\/\/doi.org\/10.1007\/s11047-021-09875-x","relation":{},"ISSN":["1567-7818","1572-9796"],"issn-type":[{"type":"print","value":"1567-7818"},{"type":"electronic","value":"1572-9796"}],"subject":[],"published":{"date-parts":[[2021,11,17]]},"assertion":[{"value":"30 September 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 November 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}