{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T07:43:26Z","timestamp":1769845406181,"version":"3.49.0"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2017,5,4]],"date-time":"2017-05-04T00:00:00Z","timestamp":1493856000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2017,5,4]],"date-time":"2017-05-04T00:00:00Z","timestamp":1493856000000},"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-1117672"],"award-info":[{"award-number":["CCF-1117672"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1555626"],"award-info":[{"award-number":["CCF-1555626"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1422152"],"award-info":[{"award-number":["CCF-1422152"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,4]]},"DOI":"10.1007\/s00453-017-0318-0","type":"journal-article","created":{"date-parts":[[2017,5,4]],"date-time":"2017-05-04T16:18:06Z","timestamp":1493914686000},"page":"1383-1409","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Optimal Staged Self-Assembly of General Shapes"],"prefix":"10.1007","volume":"80","author":[{"given":"Cameron","family":"Chalk","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eric","family":"Martinez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert","family":"Schweller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luis","family":"Vega","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew","family":"Winslow","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":[[2017,5,4]]},"reference":[{"key":"318_CR1","doi-asserted-by":"crossref","unstructured":"Abel, Z., Benbernou, N., Damian, M., Demaine, E.D., Demaine, M.L., Flatland, R., Kominers, S., Schweller, R.: Shape replication through self-assembly and RNAse enzymes. In: Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2010)","DOI":"10.1137\/1.9781611973075.85"},{"key":"318_CR2","doi-asserted-by":"crossref","unstructured":"Adleman, L., Cheng, Q., Goel, A., Huang, M.D.: Running time and program size for self-assembled squares. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC), pp. 740\u2013748 (2001)","DOI":"10.1145\/380752.380881"},{"key":"318_CR3","doi-asserted-by":"crossref","unstructured":"Behsaz, B., Ma\u0148uch, J., Stacho, L.: Turing universality of step-wise and stage assembly at temperature 1. In: DNA Computing and Molecular Programming (DNA), LNCS, vol. 7433, pp. 1\u201311. Springer (2012)","DOI":"10.1007\/978-3-642-32208-2_1"},{"key":"318_CR4","unstructured":"Cannon, S., Demaine, E.D., Demaine, M.L., Eisenstat, S., Patitz, M.J., Schweller, R., Summers, S.M., Winslow, A.: Two hands are better than one (up to constant factors): Self-assembly in the 2HAM vs. aTAM. In: Proceedings of 30th International Symposium on Theoretical Aspects of Computer Science (STACS), LIPIcs, vol. 20, pp. 172\u2013184. Schloss Dagstuhl (2013)"},{"key":"318_CR5","unstructured":"Chalk, C., Martinez, E., Schweller, R., Vega, L., Winslow, A., Wylie, T.: Optimal staged self-assembly of general shapes. In: Proceedings of the 24th Annual European Symposium on Algorithms (ESA), LIPIcs, vol.\u00a057, pp. 26:1\u201326:17. Schloss Dagstuhl (2016)"},{"key":"318_CR6","doi-asserted-by":"crossref","unstructured":"Chen, H.L., Doty, D.: Parallelism and time in hierarchical self-assembly. In: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1163\u20131182 (2012)","DOI":"10.1137\/1.9781611973099.92"},{"key":"318_CR7","doi-asserted-by":"publisher","first-page":"1493","DOI":"10.1137\/S0097539704446037","volume":"34","author":"Q Cheng","year":"2005","unstructured":"Cheng, Q., Aggarwal, G., Goldwasser, M.H., Kao, M.Y., Schweller, R.T., de Espan\u00e9s, P.M.: Complexities for generalized models of self-assembly. SIAM J. Comput. 34, 1493\u20131515 (2005)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"318_CR8","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/s11047-008-9073-0","volume":"7","author":"ED Demaine","year":"2008","unstructured":"Demaine, E.D., Demaine, M.L., Fekete, S.P., Ishaque, M., Rafalin, E., Schweller, R.T., Souvaine, D.L.: Staged self-assembly: nanomanufacture of arbitrary shapes with $${O}(1)$$ glues. Nat. Comput. 7(3), 347\u2013370 (2008)","journal-title":"Nat. Comput."},{"issue":"2","key":"318_CR9","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/s11047-012-9359-0","volume":"12","author":"ED Demaine","year":"2013","unstructured":"Demaine, E.D., Eisenstat, S., Ishaque, M., Winslow, A.: One-dimensional staged self-assembly. Nat. Comput. 12(2), 247\u2013258 (2013)","journal-title":"Nat. Comput."},{"key":"318_CR10","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Fekete, S.P., Scheffer, C., Schmidt, A.: New geometric algorithms for fully connected staged self-assembly. In: DNA Computing and Molecular Programming (DNA), LNCS, vol. 9211, pp. 104\u2013116. Springer (2015)","DOI":"10.1007\/978-3-319-21999-8_7"},{"key":"318_CR11","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Patitz, M.J., Rogers, T.A., Schweller, R.T., Woods, D.: The two-handed tile assembly model is not intrinsically universal. In: Automata, Languages and Programming (ICALP), LNCS, vol. 7965, pp. 400\u2013412. Springer (2013)","DOI":"10.1007\/978-3-642-39206-1_34"},{"key":"318_CR12","unstructured":"Demaine, E.D., Patitz, M.J., Schweller, R.T., Summers, S.M.: Self-assembly of arbitrary shapes using RNAse enzymes: meeting the Kolmogorov bound with small scale factor (extended abstract). In: Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS), LIPIcs, vol.\u00a09, pp. 201\u2013212. Schloss Dagstuhl (2011)"},{"issue":"12","key":"318_CR13","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1145\/2380656.2380675","volume":"55","author":"D Doty","year":"2012","unstructured":"Doty, D.: Theory of algorithmic self-assembly. Commun. ACM 55(12), 78\u201388 (2012)","journal-title":"Commun. ACM"},{"issue":"1","key":"318_CR14","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/s11047-015-9517-2","volume":"15","author":"D Doty","year":"2016","unstructured":"Doty, D.: Producibility in hierarchical self-assembly. Nat. Comput. 15(1), 41\u201349 (2016)","journal-title":"Nat. Comput."},{"key":"318_CR15","unstructured":"Evans, C.: Crystals that count! Physical principles and experimental investigations of DNA tile self-assembly. Ph.D. thesis, Caltech (2014)"},{"key":"318_CR16","doi-asserted-by":"crossref","unstructured":"Furcy, D., Micka, S., Summers, S.M.: Optimal program-size complexity for self-assembly at temperature 1 in 3D. In: DNA Computing and Molecular Programming (DNA), LNCS, vol. 9211, pp. 71\u201386. Springer (2015)","DOI":"10.1007\/978-3-319-21999-8_5"},{"issue":"6111","key":"318_CR17","doi-asserted-by":"publisher","first-page":"1177","DOI":"10.1126\/science.1227268","volume":"338","author":"Y Ke","year":"2012","unstructured":"Ke, Y., Ong, L.L., Shih, W.M., Yin, P.: Three-dimensional structures self-assembled from DNA bricks. Science 338(6111), 1177\u20131183 (2012)","journal-title":"Science"},{"key":"318_CR18","unstructured":"Labean, T.H., Park, S.H., Ahn, S.J., Reif, J.H.: Stepwise DNA self-assembly of fixed-size nanostructures. In: Foundations of Nanoscience, Self-Assembled Architectures, and Devices, pp. 179\u2013181 (2005)"},{"key":"318_CR19","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-49820-1","volume-title":"An Introduction to Kolmogorov Complexity and Its Applications","author":"M Li","year":"2008","unstructured":"Li, M., Vitnyi, P.M.: An Introduction to Kolmogorov Complexity and Its Applications, 3rd edn. Springer, Berlin (2008)","edition":"3"},{"issue":"3","key":"318_CR20","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1007\/s11047-012-9321-1","volume":"11","author":"J Ma\u0148uch","year":"2012","unstructured":"Ma\u0148uch, J., Stacho, L., Stoll, C.: Step-wise tile assembly with a constant number of tile types. Nat. Comput. 11(3), 535\u2013550 (2012)","journal-title":"Nat. Comput."},{"key":"318_CR21","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1007\/s00453-011-9549-7","volume":"64","author":"MJ Patitz","year":"2012","unstructured":"Patitz, M.J., Summers, S.M.: Identifying shapes using self-assembly. Algorithmica 64, 481\u2013510 (2012)","journal-title":"Algorithmica"},{"issue":"2","key":"318_CR22","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/s11047-013-9379-4","volume":"13","author":"MJ Patitz","year":"2014","unstructured":"Patitz, M.J.: An introduction to tile-based self-assembly and a survey of recent results. Nat. Comput. 13(2), 195\u2013224 (2014)","journal-title":"Nat. Comput."},{"key":"318_CR23","doi-asserted-by":"crossref","unstructured":"Rothemund, P.W.K., Winfree, E.: The program-size complexity of self-assembled squares (extended abstract). In: Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC), pp. 459\u2013468 (2000)","DOI":"10.1145\/335305.335358"},{"key":"318_CR24","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0022-5193(82)90002-9","volume":"99","author":"NC Seeman","year":"1982","unstructured":"Seeman, N.C.: Nucleic-acid junctions and lattices. J. Theor. Biol. 99, 237\u2013247 (1982)","journal-title":"J. Theor. Biol."},{"issue":"6","key":"318_CR25","doi-asserted-by":"publisher","first-page":"1544","DOI":"10.1137\/S0097539704446712","volume":"36","author":"D Soloveichik","year":"2007","unstructured":"Soloveichik, D., Winfree, E.: Complexity of self-assembled shapes. SIAM J. Comput. 36(6), 1544\u20131569 (2007)","journal-title":"SIAM J. Comput."},{"key":"318_CR26","unstructured":"Winfree, E.: Algorithmic self-assembly of DNA. Ph.D. thesis, Caltech (1998)"},{"issue":"2","key":"318_CR27","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s11047-014-9423-z","volume":"14","author":"A Winslow","year":"2015","unstructured":"Winslow, A.: Staged self-assembly and polyomino context-free grammars. Nat. Comput. 14(2), 293\u2013302 (2015)","journal-title":"Nat. Comput."},{"key":"318_CR28","doi-asserted-by":"crossref","unstructured":"Winslow, A.: A brief tour of theoretical tile self-assembly. In: Proceedings of the 22nd International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), LNCS, vol. 9664, pp. 26\u201331. Springer (2016)","DOI":"10.1007\/978-3-319-39300-1_3"},{"key":"318_CR29","doi-asserted-by":"publisher","unstructured":"Woods, D.: Intrinsic universality and the computational power of self-assembly. Philos. Trans. R. Soc. A 373(2046) (2015). doi:\n                    10.1098\/rsta.2014.0214","DOI":"10.1098\/rsta.2014.0214"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0318-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0318-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0318-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T06:29:35Z","timestamp":1589696975000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0318-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,4]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,4]]}},"alternative-id":["318"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0318-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,5,4]]},"assertion":[{"value":"13 September 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 April 2017","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 May 2017","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}