{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:15:52Z","timestamp":1763468152366},"publisher-location":"Cham","reference-count":46,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319019277"},{"type":"electronic","value":"9783319019284"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"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":[[2013]]},"DOI":"10.1007\/978-3-319-01928-4_2","type":"book-chapter","created":{"date-parts":[[2013,9,18]],"date-time":"2013-09-18T15:44:15Z","timestamp":1379519055000},"page":"16-30","source":"Crossref","is-referenced-by-count":10,"title":["Parallel Computation Using Active Self-assembly"],"prefix":"10.1007","author":[{"given":"Moya","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Doris","family":"Xin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Damien","family":"Woods","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"2_CR1","doi-asserted-by":"publisher","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 Journal on Computing\u00a034, 1493\u20131515 (2005)","journal-title":"SIAM Journal on Computing"},{"key":"2_CR2","doi-asserted-by":"crossref","unstructured":"Allender, E., Kouck\u00fd, M.: Amplifying lower bounds by means of self-reducibility. Journal of the ACM\u00a057, 14:1\u201314:36 (2010)","DOI":"10.1145\/1706591.1706594"},{"issue":"1","key":"2_CR3","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1017\/S026357471000072X","volume":"29","author":"G. Aloupis","year":"2011","unstructured":"Aloupis, G., Collette, S., Damian, M., Demaine, E., Flatland, R., Langerman, S., O\u2019rourke, J., Pinciu, V., Ramaswami, S., Sacrist\u00e1n, V., Wuhrer, S.: Efficient constant-velocity reconfiguration of crystalline robots. Robotica\u00a029(1), 59\u201371 (2011)","journal-title":"Robotica"},{"key":"2_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1007\/978-3-540-92182-0_32","volume-title":"Algorithms and Computation","author":"G. Aloupis","year":"2008","unstructured":"Aloupis, G., Collette, S., Demaine, E.D., Langerman, S., Sacrist\u00e1n, V., Wuhrer, S.: Reconfiguration of cube-style modular robots using O(logn) parallel moves. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS, vol.\u00a05369, pp. 342\u2013353. Springer, Heidelberg (2008)"},{"key":"2_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/11864219_5","volume-title":"Distributed Computing","author":"D. Angluin","year":"2006","unstructured":"Angluin, D., Aspnes, J., Eisenstat, D.: Fast computation by population protocols with a leader. In: Dolev, S. (ed.) DISC 2006. LNCS, vol.\u00a04167, pp. 61\u201375. Springer, Heidelberg (2006)"},{"key":"2_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/11944836_7","volume-title":"FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science","author":"F. Becker","year":"2006","unstructured":"Becker, F., Rapaport, I., R\u00e9mila, \u00c9.: Self-assemblying classes of shapes with a minimum number of tiles, and in optimal time. In: Arun-Kumar, S., Garg, N. (eds.) FSTTCS 2006. LNCS, vol.\u00a04337, pp. 45\u201356. Springer, Heidelberg (2006)"},{"key":"2_CR7","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1109\/TMECH.2002.806230","volume":"7","author":"Z. Butler","year":"2002","unstructured":"Butler, Z., Fitch, R., Rus, D.: Distributed control for unit-compressible robots: goal-recognition, locomotion, and splitting. IEEE\/ASME Transactions on Mechatronics\u00a07, 418\u2013430 (2002)","journal-title":"IEEE\/ASME Transactions on Mechatronics"},{"key":"2_CR8","unstructured":"Cannon, S., Demaine, E.D., Demaine, M.L., Eisenstat, S., Patitz, M.J., Schweller, R.T., Summers, S.M., Winslow, A.: Two hands are better than one (up to constant factors): Self-assembly In the 2HAM vs. aTAM. In: STACS: 30th International Symposium on Theoretical Aspects of Computer Science, pp. 172\u2013184 (2013)"},{"key":"2_CR9","doi-asserted-by":"crossref","unstructured":"Chandran, H., Gopalkrishnan, N., Reif, J.: Tile complexity of approximate squares. Algorithmica, 1\u201317 (2012)","DOI":"10.1007\/s00453-012-9620-z"},{"issue":"3","key":"2_CR10","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1007\/BF01206637","volume":"4","author":"A. Condon","year":"1994","unstructured":"Condon, A.: A theory of strict P-completeness. Computational Complexity\u00a04(3), 220\u2013241 (1994)","journal-title":"Computational Complexity"},{"key":"2_CR11","doi-asserted-by":"crossref","unstructured":"Dabby, N., Chen, H.-L.: Active self-assembly of simple units using an insertion primitive. In: SODA: Proceedings of the Twenty-fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1526\u20131536 (January 2012)","DOI":"10.1137\/1.9781611973105.110"},{"issue":"3","key":"2_CR12","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/s11047-008-9073-0","volume":"7","author":"E. Demaine","year":"2008","unstructured":"Demaine, E., Demaine, M., Fekete, S., Ishaque, M., Rafalin, E., Schweller, R., Souvaine, D.: Staged self-assembly: nanomanufacture of arbitrary shapes with O(1) glues. Natural Computing\u00a07(3), 347\u2013370 (2008)","journal-title":"Natural Computing"},{"key":"2_CR13","unstructured":"Demaine, E.D., Demaine, M.L., Fekete, S.P., Patitz, M.J., Schweller, R.T., Winslow, A., Woods, D.: One tile to rule them all: Simulating any Turing machine, tile assembly system, or tiling system with a single puzzle piece (December 2012), Arxiv preprint arXiv:1212.4756 [cs.DS]"},{"key":"2_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1007\/978-3-642-23638-9_10","volume-title":"DNA Computing and Molecular Programming","author":"E.D. Demaine","year":"2011","unstructured":"Demaine, E.D., Eisenstat, S., Ishaque, M., Winslow, A.: One-dimensional staged self-assembly. In: Cardelli, L., Shih, W. (eds.) DNA 17 2011. LNCS, vol.\u00a06937, pp. 100\u2013114. Springer, Heidelberg (2011)"},{"key":"2_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1007\/978-3-642-39206-1_34","volume-title":"Automata, Languages, and Programming","author":"E.D. Demaine","year":"2013","unstructured":"Demaine, E.D., Patitz, M.J., Rogers, T.A., Schweller, R.T., Summers, S.M., Woods, D.: The two-handed tile assembly model is not intrinsically universal. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol.\u00a07965, pp. 400\u2013412. Springer, Heidelberg (2013)"},{"key":"2_CR16","doi-asserted-by":"publisher","first-page":"3521","DOI":"10.1137\/090779152","volume":"39","author":"D. Doty","year":"2010","unstructured":"Doty, D.: Randomized self-assembly for exact shapes. SICOMP\u00a039, 3521 (2010)","journal-title":"SICOMP"},{"key":"2_CR17","doi-asserted-by":"crossref","unstructured":"Doty, D., Lutz, J.H., Patitz, M.J., Schweller, R.T., Summers, S.M., Woods, D.: The tile assembly model is intrinsically universal. In: Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, pp. 439\u2013446 (October 2012)","DOI":"10.1109\/FOCS.2012.76"},{"key":"2_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"714","DOI":"10.1007\/978-3-642-31594-7_60","volume-title":"Automata, Languages, and Programming","author":"B. Fu","year":"2012","unstructured":"Fu, B., Patitz, M.J., Schweller, R.T., Sheline, R.: Self-assembly with geometric tiles. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol.\u00a07391, pp. 714\u2013725. Springer, Heidelberg (2012)"},{"key":"2_CR19","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780195085914.001.0001","volume-title":"Limits to parallel computation: P-completeness theory","author":"R. Greenlaw","year":"1995","unstructured":"Greenlaw, R., Hoover, H.J., Ruzzo, W.L.: Limits to parallel computation: P-completeness theory. Oxford University Press, USA (1995)"},{"key":"2_CR20","unstructured":"Jonoska, N., Karpenko, D.: Active tile self-assembly, self-similar structures and recursion (2012), Arxiv preprint arXiv:1211.3085 [cs.ET]"},{"issue":"4","key":"2_CR21","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1016\/j.tcs.2008.09.054","volume":"410","author":"N. Jonoska","year":"2009","unstructured":"Jonoska, N., McColm, G.L.: Complexity classes for self-assembling flexible tiles. Theoretical Computer Science\u00a0410(4), 332\u2013346 (2009)","journal-title":"Theoretical Computer Science"},{"key":"2_CR22","doi-asserted-by":"crossref","unstructured":"Kao, M., Schweller, R.: Reducing tile complexity for self-assembly through temperature programming. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, pp. 571\u2013580. ACM (2006)","DOI":"10.1145\/1109557.1109620"},{"key":"2_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"370","DOI":"10.1007\/978-3-540-70575-8_31","volume-title":"Automata, Languages and Programming","author":"M.-Y. Kao","year":"2008","unstructured":"Kao, M.-Y., Schweller, R.T.: Randomized self-assembly for approximate shapes. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 370\u2013384. Springer, Heidelberg (2008)"},{"key":"2_CR24","unstructured":"Klavins, E.: Directed self-assembly using graph grammars. In: Foundations of Nanoscience: Self Assembled Architectures and Devices, Snowbird, UT (2004)"},{"issue":"7228","key":"2_CR25","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1038\/nature07522","volume":"457","author":"A.C. Martin","year":"2008","unstructured":"Martin, A.C., Kaschube, M., Wieschaus, E.F.: Pulsed contractions of an actin\u2013myosin network drive apical constriction. Nature\u00a0457(7228), 495\u2013499 (2008)","journal-title":"Nature"},{"issue":"1","key":"2_CR26","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1109\/MRA.2007.339607","volume":"14","author":"S. Murata","year":"2007","unstructured":"Murata, S., Kurokawa, H.: Self-reconfigurable robots. IEEE Robotics & Automation Magazine\u00a014(1), 71\u201378 (2007)","journal-title":"IEEE Robotics & Automation Magazine"},{"issue":"1","key":"2_CR27","first-page":"3","volume":"4","author":"N. Murphy","year":"2008","unstructured":"Murphy, N., Naughton, T.J., Woods, D., Henley, B., McDermott, K., Duffy, E., van der Burgt, P.J., Woods, N.: Implementations of a model of physical sorting. International Journal of Unconventional Computing\u00a04(1), 3\u201312 (2008)","journal-title":"International Journal of Unconventional Computing"},{"key":"2_CR28","unstructured":"Murphy, N., Woods, D.: AND and\/or OR: Uniform polynomial-size circuits. In: MCU: Machines, Computations and Universality (accepted, 2013)"},{"key":"2_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1007\/11786986_13","volume-title":"Automata, Languages and Programming","author":"T. Neary","year":"2006","unstructured":"Neary, T., Woods, D.: P-completeness of cellular automaton rule 110. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol.\u00a04051, pp. 132\u2013143. Springer, Heidelberg (2006)"},{"key":"2_CR30","doi-asserted-by":"crossref","unstructured":"Padilla, J., Liu, W., Seeman, N.: Hierarchical self assembly of patterns from the Robinson tilings: DNA tile design in an enhanced tile assembly model. Natural Computing, 1\u201316 (2011)","DOI":"10.1007\/s11047-011-9268-7"},{"key":"2_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1007\/978-3-642-39074-6_17","volume-title":"Unconventional Computation and Natural Computation","author":"J. Padilla","year":"2013","unstructured":"Padilla, J., Patitz, M., Pena, R., Schweller, R., Seeman, N., Sheline, R., Summers, S., Zhong, X.: Asynchronous signal passing for tile self-assembly: Fuel efficient computation and efficient assembly of shapes. In: Mauri, G., Dennunzio, A., Manzoni, L., Porreca, A.E. (eds.) UCNC 2013. LNCS, vol.\u00a07956, pp. 174\u2013185. Springer, Heidelberg (2013)"},{"key":"2_CR32","unstructured":"Papadimitriou, C.M.: Computational complexity, 1st edn. Addison-Wesley Publishing Company, Inc. (1994)"},{"key":"2_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1007\/978-3-642-32894-7_6","volume-title":"Unconventional Computation and Natural Computation","author":"M.J. Patitz","year":"2012","unstructured":"Patitz, M.J.: An introduction to tile-based self-assembly. In: Durand-Lose, J., Jonoska, N. (eds.) UCNC 2012. LNCS, vol.\u00a07445, pp. 34\u201362. Springer, Heidelberg (2012)"},{"key":"2_CR34","doi-asserted-by":"crossref","unstructured":"Prusinkiewicz, P., Lindenmayer, A.: The algorithmic beauty of plants. Springer (1990)","DOI":"10.1007\/978-1-4613-8476-2"},{"key":"2_CR35","doi-asserted-by":"crossref","unstructured":"Reif, J., Slee, S.: Optimal kinodynamic motion planning for 2D reconfiguration of self-reconfigurable robots. Robot. Sci. Syst. (2007)","DOI":"10.15607\/RSS.2007.III.020"},{"key":"2_CR36","doi-asserted-by":"crossref","unstructured":"Rothemund, P.W.K., Winfree, E.: The program-size complexity of self-assembled squares (extended abstract). In: STOC: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pp. 459\u2013468. ACM Press (2000)","DOI":"10.1145\/335305.335358"},{"issue":"1","key":"2_CR37","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1023\/A:1026504804984","volume":"10","author":"D. Rus","year":"2001","unstructured":"Rus, D., Vona, M.: Crystalline robots: Self-reconfiguration with compressible unit modules. Autonomous Robots\u00a010(1), 107\u2013124 (2001)","journal-title":"Autonomous Robots"},{"issue":"4","key":"2_CR38","doi-asserted-by":"publisher","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. Natural Computing\u00a07(4), 615\u2013633 (2008)","journal-title":"Natural Computing"},{"key":"2_CR39","doi-asserted-by":"crossref","unstructured":"Summers, S.: Reducing tile complexity for the self-assembly of scaled shapes through temperature programming. Algorithmica, 1\u201320 (2012)","DOI":"10.1007\/s00453-011-9522-5"},{"key":"2_CR40","doi-asserted-by":"crossref","unstructured":"Vollmer, H.: Introduction to Circuit Complexity: A Uniform Approach. Springer-Verlag New York, Inc. (1999)","DOI":"10.1007\/978-3-662-03927-4"},{"key":"2_CR41","unstructured":"Winfree, E.: Algorithmic Self-Assembly of DNA. PhD thesis, California Institute of Technology (June 1998)"},{"key":"2_CR42","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"777","DOI":"10.1007\/11602613_78","volume-title":"Algorithms and Computation","author":"D. Woods","year":"2005","unstructured":"Woods, D.: Upper bounds on the computational power of an optical model of computation. In: Deng, X., Du, D.-Z. (eds.) ISAAC 2005. LNCS, vol.\u00a03827, pp. 777\u2013788. Springer, Heidelberg (2005)"},{"key":"2_CR43","doi-asserted-by":"crossref","unstructured":"Woods, D., Chen, H.-L., Goodfriend, S., Dabby, N., Winfree, E., Yin, P.: Active self-assembly of algorithmic shapes and patterns in polylogarithmic time. In: ITCS 2013: Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, pp. 353\u2013354. ACM (2013), Full version: arXiv:1301.2626 [cs.DS]","DOI":"10.1145\/2422436.2422476"},{"key":"2_CR44","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1007\/978-3-540-85673-3_6","volume-title":"Optical SuperComputing","author":"D. Woods","year":"2008","unstructured":"Woods, D., Naughton, T.J.: Parallel and sequential optical computing. In: Dolev, S., Haist, T., Oltean, M. (eds.) OSC 2008. LNCS, vol.\u00a05172, pp. 70\u201386. Springer, Heidelberg (2008)"},{"key":"2_CR45","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1038\/35020524","volume":"406","author":"B. Yurke","year":"2000","unstructured":"Yurke, B., Turberfield, A.J., Mills Jr., A.P., Simmel, F.C., Nuemann, J.L.: A DNA-fuelled molecular machine made of DNA. Nature\u00a0406, 605\u2013608 (2000)","journal-title":"Nature"},{"issue":"1","key":"2_CR46","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0304-3975(93)90252-O","volume":"107","author":"C. Lvarez","year":"1993","unstructured":"Lvarez, C., Jenner, B.: A very hard log-space counting class. Theoretical Computer Science\u00a0107(1), 3\u201330 (1993)","journal-title":"Theoretical Computer 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-01928-4_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,6]],"date-time":"2022-03-06T10:37:39Z","timestamp":1646563059000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-01928-4_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783319019277","9783319019284"],"references-count":46,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-01928-4_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}