{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T06:21:15Z","timestamp":1725862875375},"publisher-location":"Cham","reference-count":35,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319439938"},{"type":"electronic","value":"9783319439945"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-43994-5_11","type":"book-chapter","created":{"date-parts":[[2016,8,13]],"date-time":"2016-08-13T09:34:57Z","timestamp":1471080897000},"page":"165-182","source":"Crossref","is-referenced-by-count":6,"title":["Time Complexity of Computation and Construction in the Chemical Reaction Network-Controlled Tile Assembly Model"],"prefix":"10.1007","author":[{"given":"Nicholas","family":"Schiefer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erik","family":"Winfree","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,8,14]]},"reference":[{"key":"11_CR1","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 2001, pp. 740\u2013748 (2001)","DOI":"10.1145\/380752.380881"},{"key":"11_CR2","doi-asserted-by":"crossref","first-page":"1493","DOI":"10.1137\/S0097539704445202","volume":"34","author":"G Aggarwal","year":"2005","unstructured":"Aggarwal, G., Cheng, Q., Goldwasser, M.H., Kao, M.Y., de Espanes, P.M., Schweller, R.T.: Complexities for generalized models of self-assembly. SIAM J. Comput. 34, 1493\u20131515 (2005)","journal-title":"SIAM J. Comput."},{"key":"11_CR3","doi-asserted-by":"crossref","first-page":"6054","DOI":"10.1073\/pnas.0808736106","volume":"106","author":"RD Barish","year":"2009","unstructured":"Barish, R.D., Schulman, R., Rothemund, P.W.K., Winfree, E.: An information-bearing seed for nucleating algorithmic self-assembly. Proc. Natl. Acad. Sci. 106, 6054\u20136059 (2009)","journal-title":"Proc. Natl. Acad. Sci."},{"key":"11_CR4","doi-asserted-by":"crossref","first-page":"905","DOI":"10.1007\/BF02084158","volume":"21","author":"CH Bennett","year":"1982","unstructured":"Bennett, C.H.: The thermodynamics of computation - a review. Int. J. Theoret. Phys. 21, 905\u2013940 (1982)","journal-title":"Int. J. Theoret. Phys."},{"key":"11_CR5","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1017\/S0960129512000102","volume":"23","author":"L Cardelli","year":"2013","unstructured":"Cardelli, L.: Two-domain DNA strand displacement. Math. Struct. Comput. Sci. 23, 247\u2013271 (2013)","journal-title":"Math. Struct. Comput. Sci."},{"key":"11_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/978-3-540-85101-1_6","volume-title":"Algebraic Biology","author":"L Cardelli","year":"2008","unstructured":"Cardelli, L., Zavattaro, G.: On the computational power of biochemistry. In: Horimoto, K., Regensburger, G., Rosenkranz, M., Yoshida, H. (eds.) AB 2008. LNCS, vol. 5147, pp. 65\u201380. Springer, Heidelberg (2008)"},{"key":"11_CR7","doi-asserted-by":"crossref","first-page":"755","DOI":"10.1038\/nnano.2013.189","volume":"8","author":"YJ Chen","year":"2013","unstructured":"Chen, Y.J., Dalchau, N., Srinivas, N., Cardelli, L., Soloveichik, D., Seelig, G.: Programmable chemical controllers made from DNA. Nat. Nanotechnol. 8, 755\u2013762 (2013)","journal-title":"Nat. Nanotechnol."},{"key":"11_CR8","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1007\/s11047-013-9403-8","volume":"13","author":"A Condon","year":"2014","unstructured":"Condon, A., Kirkpatrick, B., Ma\u0148uch, J.: Reachability bounds for chemical reaction networks and strand displacement systems. Nat. Comput. 13, 499\u2013516 (2014)","journal-title":"Nat. Comput."},{"key":"11_CR9","doi-asserted-by":"crossref","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, 78\u201388 (2012)","journal-title":"Commun. ACM"},{"key":"11_CR10","doi-asserted-by":"crossref","first-page":"2340","DOI":"10.1021\/j100540a008","volume":"81","author":"DT Gillespie","year":"1977","unstructured":"Gillespie, D.T.: Exact stochastic simulation of coupled chemical reactions. J. Phys. Chem. 81, 2340\u20132361 (1977)","journal-title":"J. Phys. Chem."},{"key":"11_CR11","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1146\/annurev.physchem.58.032806.104637","volume":"58","author":"DT Gillespie","year":"2007","unstructured":"Gillespie, D.T.: Stochastic simulation of chemical kinetics. Annu. Rev. Phys. Chem. 58, 35\u201355 (2007)","journal-title":"Annu. Rev. Phys. Chem."},{"key":"11_CR12","doi-asserted-by":"crossref","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, 1177\u20131183 (2012)","journal-title":"Science"},{"key":"11_CR13","doi-asserted-by":"crossref","unstructured":"Kurtz, S., Mahaney, S., Royer, J., Simon, J.: Biological computing. In: Complexity Theory Retrospective II, pp. 179\u2013195 (1997)","DOI":"10.1007\/978-1-4612-1872-2_8"},{"key":"11_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1007\/978-3-642-23638-9_12","volume-title":"DNA Computing and Molecular Programming","author":"MR Lakin","year":"2011","unstructured":"Lakin, M.R., Phillips, A.: Modelling, simulating and verifying turing-powerful strand displacement systems. In: Cardelli, L., Shih, W. (eds.) DNA 17 2011. LNCS, vol. 6937, pp. 130\u2013144. Springer, Heidelberg (2011)"},{"key":"11_CR15","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/j.tcs.2015.06.033","volume":"632","author":"MR Lakin","year":"2016","unstructured":"Lakin, M.R., Stefanovic, D., Phillips, A.: Modular verification of chemical reaction network encodings via serializability analysis. Theoret. Comput. Sci. 632, 21\u201342 (2016)","journal-title":"Theoret. Comput. Sci."},{"key":"11_CR16","doi-asserted-by":"crossref","unstructured":"Lipton, R.J.: DNA computations can have global memory. In: International Conference on Computer Design: VLSI in Computers and Processor, pp. 344\u2013347 (1996)","DOI":"10.1109\/ICCD.1996.563577"},{"key":"11_CR17","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/s11047-013-9379-4","volume":"13","author":"MJ Patitz","year":"2013","unstructured":"Patitz, M.J.: An introduction to tile-based self-assembly and a survey of recent results. Nat. Comput. 13, 195\u2013224 (2013)","journal-title":"Nat. Comput."},{"key":"11_CR18","doi-asserted-by":"crossref","first-page":"S419","DOI":"10.1098\/rsif.2009.0072.focus","volume":"6","author":"A Phillips","year":"2009","unstructured":"Phillips, A., Cardelli, L.: A programming language for composable DNA circuits. J. R. Soc. Interface 6, S419\u2013S436 (2009)","journal-title":"J. R. Soc. Interface"},{"key":"11_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1007\/978-3-642-18305-8_12","volume-title":"DNA Computing and Molecular Programming","author":"L Qian","year":"2011","unstructured":"Qian, L., Soloveichik, D., Winfree, E.: Efficient turing-universal computation with DNA polymers. In: Sakakibara, Y., Mi, Y. (eds.) DNA 16 2010. LNCS, vol. 6518, pp. 123\u2013140. Springer, Heidelberg (2011)"},{"key":"11_CR20","doi-asserted-by":"crossref","first-page":"1196","DOI":"10.1126\/science.1200520","volume":"332","author":"L Qian","year":"2011","unstructured":"Qian, L., Winfree, E.: Scaling up digital circuit computation with DNA strand displacement cascades. Science 332, 1196\u20131201 (2011)","journal-title":"Science"},{"key":"11_CR21","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1038\/nature10262","volume":"475","author":"L Qian","year":"2011","unstructured":"Qian, L., Winfree, E., Bruck, J.: Neural network computation with DNA strand displacement cascades. Nature 475, 368\u2013372 (2011)","journal-title":"Nature"},{"key":"11_CR22","doi-asserted-by":"crossref","first-page":"e424","DOI":"10.1371\/journal.pbio.0020424","volume":"2","author":"PWK Rothemund","year":"2004","unstructured":"Rothemund, P.W.K., Papadakis, N., Winfree, E.: Algorithmic self-assembly of DNA Sierpinski triangles. PLoS Biol. 2, e424 (2004)","journal-title":"PLoS Biol."},{"key":"11_CR23","doi-asserted-by":"crossref","unstructured":"Rothemund, P.W.K., Winfree, E.: The program-size complexity of self-assembled squares. In: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, STOC 2000, pp. 459\u2013468 (2000)","DOI":"10.1145\/335305.335358"},{"key":"11_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1007\/978-3-319-21999-8_3","volume-title":"DNA Computing and Molecular Programming","author":"N Schiefer","year":"2015","unstructured":"Schiefer, N., Winfree, E.: Universal computation and optimal construction in the chemical reaction network-controlled tile assembly model. In: Phillips, A., Yin, P. (eds.) DNA 2015. LNCS, vol. 9211, pp. 34\u201354. Springer, Heidelberg (2015)"},{"key":"11_CR25","doi-asserted-by":"crossref","first-page":"1585","DOI":"10.1126\/science.1132493","volume":"314","author":"G Seelig","year":"2006","unstructured":"Seelig, G., Soloveichik, D., Zhang, D.Y., Winfree, E.: Enzyme-free nucleic acid logic circuits. Science 314, 1585\u20131588 (2006)","journal-title":"Science"},{"key":"11_CR26","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1007\/s11047-008-9067-y","volume":"7","author":"D Soloveichik","year":"2008","unstructured":"Soloveichik, D., Cook, M., Winfree, E., Bruck, J.: Computation with finite stochastic chemical reaction networks. Nat. Comput. 7, 615\u2013633 (2008)","journal-title":"Nat. Comput."},{"key":"11_CR27","doi-asserted-by":"crossref","first-page":"5393","DOI":"10.1073\/pnas.0909380107","volume":"107","author":"D Soloveichik","year":"2010","unstructured":"Soloveichik, D., Seelig, G., Winfree, E.: DNA as a universal substrate for chemical kinetics. Proc. Natl. Acad. Sci. 107, 5393\u20135398 (2010)","journal-title":"Proc. Natl. Acad. Sci."},{"key":"11_CR28","doi-asserted-by":"crossref","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, 1544\u20131569 (2007)","journal-title":"SIAM J. Comput."},{"key":"11_CR29","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1038\/nature11075","volume":"485","author":"B Wei","year":"2012","unstructured":"Wei, B., Dai, M., Yin, P.: Complex shapes self-assembled from single-stranded DNA tiles. Nature 485, 623\u2013626 (2012)","journal-title":"Nature"},{"key":"11_CR30","doi-asserted-by":"crossref","unstructured":"Winfree, E.: On the computational power of DNA annealing and ligation. In: DNA Computers. DIMACS Series in Discrete Mathematics and Computer Science, vol. 27, pp. 199\u2013221. American Mathematical Society (1996)","DOI":"10.1090\/dimacs\/027\/09"},{"key":"11_CR31","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1038\/28998","volume":"394","author":"E Winfree","year":"1998","unstructured":"Winfree, E., Liu, F., Wenzler, L.A., Seeman, N.C.: Design and self-assembly of two-dimensional DNA crystals. Nature 394, 539\u2013544 (1998)","journal-title":"Nature"},{"key":"11_CR32","doi-asserted-by":"crossref","unstructured":"Winfree, E., Yang, X., Seeman, N.C.: Universal computation via self-assembly of DNA: some theory and experiments. In: DNA Based Computers II. DIMACS Series in Discrete Mathematics and Computer Science, vol. 44, pp. 191\u2013213. American Mathematical Society (1999)","DOI":"10.1090\/dimacs\/044\/16"},{"key":"11_CR33","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1038\/nature06451","volume":"451","author":"P Yin","year":"2008","unstructured":"Yin, P., Choi, H.M.T., Calvert, C.R., Pierce, N.A.: Programming biomolecular self-assembly pathways. Nature 451, 318\u2013322 (2008)","journal-title":"Nature"},{"key":"11_CR34","doi-asserted-by":"crossref","unstructured":"Zhang, D.Y., Hariadi, R.F., Choi, H.M.T., Winfree, E.: Integrating DNA strand-displacement circuitry with DNA tile self-assembly. Nat. Commun. 4, Article no. 1965 (2013)","DOI":"10.1038\/ncomms2965"},{"key":"11_CR35","doi-asserted-by":"crossref","first-page":"1121","DOI":"10.1126\/science.1148532","volume":"318","author":"DY Zhang","year":"2007","unstructured":"Zhang, D.Y., Turberfield, A.J., Yurke, B., Winfree, E.: Engineering entropy-driven reactions and networks catalyzed by DNA. Science 318, 1121\u20131125 (2007)","journal-title":"Science"}],"container-title":["Lecture Notes in Computer Science","DNA Computing and Molecular Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-43994-5_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,12]],"date-time":"2019-09-12T14:32:03Z","timestamp":1568298723000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-43994-5_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319439938","9783319439945"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-43994-5_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}