{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,18]],"date-time":"2026-09-18T02:30:16Z","timestamp":1789698616440,"version":"4.0.1"},"reference-count":53,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2014,7,6]],"date-time":"2014-07-06T00:00:00Z","timestamp":1404604800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Nat Comput"],"published-print":{"date-parts":[[2015,6]]},"DOI":"10.1007\/s11047-014-9432-y","type":"journal-article","created":{"date-parts":[[2014,7,5]],"date-time":"2014-07-05T11:30:02Z","timestamp":1404559802000},"page":"225-250","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Parallel computation using active self-assembly"],"prefix":"10.1007","volume":"14","author":[{"given":"Moya","family":"Chen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Doris","family":"Xin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Damien","family":"Woods","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2014,7,6]]},"reference":[{"key":"9432_CR1","doi-asserted-by":"crossref","first-page":"1493","DOI":"10.1137\/S0097539704445202","volume":"34","author":"G Aggarwal","year":"2005","unstructured":"Aggarwal G, Cheng Q, Goldwasser MH, Kao M-Y, de Espanes PM, Schweller RT (2005) Complexities for generalized models of self-assembly. SIAM J Comput 34:1493\u20131515","journal-title":"SIAM J Comput"},{"key":"9432_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1706591.1706594","volume":"14","author":"E Allender","year":"2010","unstructured":"Allender E, Kouck\u00fd M (2010) Amplifying lower bounds by means of self-reducibility. JACM 14:1\u201336","journal-title":"JACM"},{"key":"9432_CR3","unstructured":"Aloupis G, Collette S, Demaine ED, Langerman S, Sacrist\u00e1n V, Wuhrer S (2008) Reconfiguration of cube-style modular robots using $$O(\\log n)$$ O ( log n ) parallel moves. In: ISAAC: Proc. of the 19th Annual International Symposium on Algorithms and Computation, pp 342\u2013353"},{"issue":"1","key":"9432_CR4","doi-asserted-by":"crossref","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 (2011) Efficient constant-velocity reconfiguration of crystalline robots. Robotica 29(1):59\u201371","journal-title":"Robotica"},{"key":"9432_CR5","doi-asserted-by":"crossref","unstructured":"Becker F, Remila E, Rapaport I (2006) Self-assemblying classes of shapes, fast and with minimal number of tiles. In: Proceedings of the 26th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2006), vol 4337 of LNCS. Springer, pp 45\u201356","DOI":"10.1007\/11944836_7"},{"key":"9432_CR6","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1109\/TMECH.2002.806230","volume":"7","author":"Z Butler","year":"2002","unstructured":"Butler Z, Fitch R, Rus D (2002) Distributed control for unit-compressible robots: goal-recognition, locomotion, and splitting. IEEE\/ASME Trans Mechatron 7:418\u2013430","journal-title":"IEEE\/ASME Trans Mechatron"},{"key":"9432_CR7","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: STACS: 30th International Symposium on Theoretical Aspects of Computer, Science, pp 172\u2013184"},{"issue":"1","key":"9432_CR8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00453-012-9620-z","volume":"66","author":"H Chandran","year":"2012","unstructured":"Chandran H, Gopalkrishnan N, Reif J (2012) Tile complexity of approximate squares. Algorithmica 66(1):1\u201317","journal-title":"Algorithmica"},{"issue":"3","key":"9432_CR9","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1007\/BF01206637","volume":"4","author":"A Condon","year":"1994","unstructured":"Condon A (1994) A theory of strict P-completeness. Comput Complex 4(3):220\u2013241","journal-title":"Comput Complex"},{"key":"9432_CR10","unstructured":"Dabby N, Chen H-L (2012) Active self-assembly of simple units using an insertion primitive. In: SODA: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, pp 1526\u20131536"},{"issue":"3","key":"9432_CR11","doi-asserted-by":"crossref","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 (2008) Staged self-assembly: nanomanufacture of arbitrary shapes with $${O}(1)$$ O ( 1 ) glues. Nat Comput 7(3):347\u2013370","journal-title":"Nat Comput"},{"key":"9432_CR12","doi-asserted-by":"crossref","unstructured":"Demaine ED, Eisenstat S, Ishaque M, Winslow A (2011) One-dimensional staged self-assembly. In: DNA: 17th Intl Conf on DNA Computing & Molecular Programming, vol 6937 of LNCS. Pasadena, pp 100\u2013114","DOI":"10.1007\/978-3-642-23638-9_10"},{"key":"9432_CR13","doi-asserted-by":"crossref","unstructured":"Demaine ED, Patitz MJ, Rogers TA, Schweller RT, Summers SM, Woods D (2013) The two-handed tile assembly model is not intrinsically universal. In: ICALP: 40th International Colloquium on Automata, Languages and Programming. Proceedings, part 1, vol 7965 of LNCS. Riga, Latvia, pp 400\u2013412. arXiv:1306.6710 [cs.CG]","DOI":"10.1007\/978-3-642-39206-1_34"},{"key":"9432_CR14","doi-asserted-by":"crossref","unstructured":"Demaine ED, Demaine ML, Fekete SP, Patitz MJ, Schweller RT, Winslow A, Woods D (2014) One tile to rule them all: simulating any Turing machine, tile assembly system, or tiling system with a single puzzle piece. In: ICALP: Proceedings of the 41st International Colloquium on Automata, Languages, and Programming. arXiv:1212.4756 [cs.DS]","DOI":"10.1007\/978-3-662-43948-7_31"},{"key":"9432_CR15","doi-asserted-by":"crossref","first-page":"3521","DOI":"10.1137\/090779152","volume":"39","author":"D Doty","year":"2010","unstructured":"Doty D (2010) Randomized self-assembly for exact shapes. SICOMP 39:3521","journal-title":"SICOMP"},{"key":"9432_CR16","unstructured":"Doty D, Lutz JH, Patitz MJ, Summers SM, Woods D (2009) Intrinsic universality in self-assembly. In: STACS: Proceedings of the 27th International Symposium on Theoretical Aspects of Computer, Science, pp 275\u2013286"},{"key":"9432_CR17","doi-asserted-by":"crossref","unstructured":"Doty D, Lutz JH, Patitz MJ, Schweller RT, Summers SM, Woods D (2012) The tile assembly model is intrinsically universal. In: FOCS: Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer, Science, pp 439\u2013446","DOI":"10.1109\/FOCS.2012.76"},{"key":"9432_CR18","doi-asserted-by":"crossref","unstructured":"Fu B, Patitz M, Schweller R, Sheline B (2012) Self-assembly with geometric tiles. In: ICALP: The 39th International Colloquium on Automata, Languages and Programming, vol 7391 of LNCS. Springer, pp 714\u2013725","DOI":"10.1007\/978-3-642-31594-7_60"},{"issue":"1","key":"9432_CR19","doi-asserted-by":"crossref","first-page":"404","DOI":"10.1016\/0378-4371(92)90283-V","volume":"188","author":"D Gillespie","year":"1992","unstructured":"Gillespie D (1992) A rigorous derivation of the chemical master equation. Phys A 188(1):404\u2013425","journal-title":"Phys A"},{"key":"9432_CR20","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 HJ, Ruzzo WL (1995) Limits to parallel computation: P-completeness theory. Oxford University Press, USA"},{"key":"9432_CR21","doi-asserted-by":"crossref","unstructured":"Hendricks J, Patitz MJ (2013) On the equivalence of cellular automata and the tile assembly model. In: MCU: Proceedings of Machines, Computations and Universality. University of Z\u00fcrich, Switzerland. September 9\u201312, Electronic Proceedings in Theoretical Computer Science, vol 128, pp 167\u2013189","DOI":"10.4204\/EPTCS.128.21"},{"key":"9432_CR22","doi-asserted-by":"crossref","unstructured":"Hendricks J, Padilla JE, Patitz MJ, Rogers TA (2013) Signal transmission across tile assemblies: 3D static tiles simulate active self-assembly by 2D signal-passing tiles. In: DNA19: The 19th International Conference on DNA Computing and Molecular Programming, vol 8141 of LNCS. Springer. arXiv:1306.5005 [cs.ET]","DOI":"10.1007\/978-3-319-01928-4_7"},{"issue":"4","key":"9432_CR23","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1016\/j.tcs.2008.09.054","volume":"410","author":"N Jonoska","year":"2009","unstructured":"Jonoska N, McColm GL (2009) Complexity classes for self-assembling flexible tiles. Theoret Comput Sci 410(4):332\u2013346","journal-title":"Theoret Comput Sci"},{"key":"9432_CR24","unstructured":"Jonoska N, Karpenko D (2012) Active tile self-assembly, self-similar structures and recursion. arXiv:1211.3085 [cs.ET]"},{"key":"9432_CR25","doi-asserted-by":"crossref","unstructured":"Kao M., Schweller R. (2006) Reducing tile complexity for self-assembly through temperature programming. In: SODA: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, pp 571\u2013580","DOI":"10.1145\/1109557.1109620"},{"key":"9432_CR26","doi-asserted-by":"crossref","unstructured":"Kao M, Schweller R (2008) Randomized self-assembly for approximate shapes. In ICALP: Proceedings of the 35th International Colloquium on Automata, Languages and Programming, vol 5125 of LNCS. Springer, pp 370\u2013384","DOI":"10.1007\/978-3-540-70575-8_31"},{"key":"9432_CR27","doi-asserted-by":"crossref","unstructured":"Keenan A, Schweller R, Sherman M, Zhong X (2014) Fast arithmetic in algorithmic self-assembly. In: UCNC : the 13th International Conference on Unconventional Computation and Natural Computation. arXiv:1303.2416 [cs.DS]","DOI":"10.1007\/978-3-319-08123-6_20"},{"key":"9432_CR28","unstructured":"Klavins E (2004) Directed self-assembly using graph grammars. Self Assembled Architectures and Devices, Snowbird, UT, In Foundations of Nanoscience"},{"key":"9432_CR29","doi-asserted-by":"crossref","unstructured":"Malchik C, Winslow A (2014) Tight bounds for active self-assembly using an insertion primitive. The 22nd European Symposium on Algorithms. arXiv:1401.0359 [cs.FL]","DOI":"10.1007\/978-3-662-44777-2_56"},{"issue":"7228","key":"9432_CR30","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1038\/nature07522","volume":"457","author":"AC Martin","year":"2008","unstructured":"Martin AC, Kaschube M, Wieschaus EF (2008) Pulsed contractions of an actin-myosin network drive apical constriction. Nature 457(7228):495\u2013499","journal-title":"Nature"},{"key":"9432_CR31","doi-asserted-by":"crossref","unstructured":"Meunier P-E, Patitz MJ, Summers SM, Theyssier G, Winslow A, Woods D (2014) Intrinsic universality in tile self-assembly requires cooperation. In: SODA: ACM-SIAM Symposium on Discrete Algorithms, pp 752\u2013771. arXiv:1304.1679 [cs.CC]","DOI":"10.1137\/1.9781611973402.56"},{"issue":"1","key":"9432_CR32","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1109\/MRA.2007.339607","volume":"14","author":"S Murata","year":"2007","unstructured":"Murata S, Kurokawa H (2007) Self-reconfigurable robots. IEEE Robot Autom Mag 14(1):71\u201378","journal-title":"IEEE Robot Autom Mag"},{"key":"9432_CR33","doi-asserted-by":"crossref","unstructured":"Murphy N, Woods D (2013) AND and\/or OR: uniform polynomial-size circuits. In MCU: Machines, Computations and Universality, vol 128, pp 150\u2013166, EPTCS. arXiv:1212.3282","DOI":"10.4204\/EPTCS.128.20"},{"issue":"1","key":"9432_CR34","first-page":"3","volume":"4","author":"N Murphy","year":"2008","unstructured":"Murphy N, Naughton TJ, Woods D, Henley B, McDermott K, Duffy E, van der Burgt PJ, Woods N (2008) Implementations of a model of physical sorting. Int J Unconv Comput 4(1):3\u201312","journal-title":"Int J Unconv Comput"},{"key":"9432_CR35","doi-asserted-by":"crossref","unstructured":"Neary T, Woods D (2006) P-completeness of cellular automaton rule 110. In: ICALP: The 33rd International Colloquium on Automata, Languages and Programming, vol 4051 of LNCS. Springer, pp 132\u2013143","DOI":"10.1007\/11786986_13"},{"issue":"2","key":"9432_CR36","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1007\/s11047-011-9268-7","volume":"11","author":"J Padilla","year":"2011","unstructured":"Padilla J, Liu W, Seeman N (2011) Hierarchical self assembly of patterns from the Robinson tilings: DNA tile design in an enhanced tile assembly model. Nat Comput 11(2):323\u2013338","journal-title":"Nat Comput"},{"key":"9432_CR37","doi-asserted-by":"crossref","unstructured":"Padilla J, Patitz M, Pena R, Schweller R, Seeman N, Sheline R, Summers S, Zhong X (2013) Asynchronous signal passing for tile self-assembly: fuel efficient computation and efficient assembly of shapes. In Unconventional Computation and Natural Computation, vol 7956 of LNCS. Springer, pp 174\u2013185","DOI":"10.1007\/978-3-642-39074-6_17"},{"key":"9432_CR38","volume-title":"Computational complexity","author":"CM Papadimitriou","year":"1994","unstructured":"Papadimitriou CM (1994) Computational complexity. Addison-Wesley, New York"},{"key":"9432_CR39","doi-asserted-by":"crossref","unstructured":"Patitz MJ (2012) An introduction to tile-based self-assembly. In: Unconventional Computation and Natural Computation, vol 7445 LNCS. Springer, pp 34\u201362","DOI":"10.1007\/978-3-642-32894-7_6"},{"key":"9432_CR40","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-8476-2","volume-title":"The algorithmic beauty of plants","author":"P Prusinkiewicz","year":"1990","unstructured":"Prusinkiewicz P, Lindenmayer A (1990) The algorithmic beauty of plants. Springer, New York"},{"issue":"2","key":"9432_CR41","first-page":"81","volume":"12","author":"J Reif","year":"2007","unstructured":"Reif J, Slee S (2007) Optimal kinodynamic motion planning for 2D reconfiguration of self-reconfigurable robots. Robot Sci Syst 12(2):81\u2013115","journal-title":"Robot Sci Syst"},{"key":"9432_CR42","unstructured":"Rothemund PWK, Winfree E (2000) The program-size complexity of self-assembled squares (extended abstract). In: STOC: Proceedings of the thirty-second annual ACM symposium on Theory of computing. ACM Press, pp 459\u2013468"},{"issue":"1","key":"9432_CR43","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1023\/A:1026504804984","volume":"10","author":"D Rus","year":"2001","unstructured":"Rus D, Vona M (2001) Crystalline robots: self-reconfiguration with compressible unit modules. Auton Robots 10(1):107\u2013124","journal-title":"Auton Robots"},{"issue":"1","key":"9432_CR44","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/s11047-004-3379-3","volume":"5","author":"D Schultes","year":"2006","unstructured":"Schultes D (2006) Rainbow sort: sorting at the speed of light. Nat Comput 5(1):67\u201382","journal-title":"Nat Comput"},{"issue":"4","key":"9432_CR45","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 (2008) Computation with finite stochastic chemical reaction networks. Nat Comput 7(4):615\u2013633","journal-title":"Nat Comput"},{"key":"9432_CR46","first-page":"1","volume":"4","author":"S Summers","year":"2012","unstructured":"Summers S (2012) Reducing tile complexity for the self-assembly of scaled shapes through temperature programming. Algorithmica 4:1\u201320","journal-title":"Algorithmica"},{"key":"9432_CR47","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03927-4","volume-title":"Introduction to circuit complexity: a uniform approach","author":"H Vollmer","year":"1999","unstructured":"Vollmer H (1999) Introduction to circuit complexity: a uniform approach. Springer, New York"},{"key":"9432_CR48","unstructured":"Winfree E (1988) Algorithmic Self-assembly of DNA. Ph.D. thesis, California Institute of Technology"},{"key":"9432_CR49","doi-asserted-by":"crossref","unstructured":"Woods D (2005) Upper bounds on the computational power of an optical model of computation. In: Algorithms and Computation. Springer, pp 777\u2013788","DOI":"10.1007\/11602613_78"},{"key":"9432_CR50","doi-asserted-by":"crossref","unstructured":"Woods D (2013) Intrinsic universality and the computational power of self-assembly. In: MCU: Proceedings of Machines, Computations and Universality, vol 128. Univ. of Z\u00fcrich, Switzerland. Sept 9\u201312, Electronic Proceedings in Theoretical Computer Science, pp 16\u201322","DOI":"10.4204\/EPTCS.128.5"},{"key":"9432_CR51","doi-asserted-by":"crossref","unstructured":"Woods D, Naughton TJ (2008) Parallel and sequential optical computing. In: Optical supercomputing, vol 5172 of LNCS. Springer, pp 70\u201386","DOI":"10.1007\/978-3-540-85673-3_6"},{"key":"9432_CR52","doi-asserted-by":"crossref","unstructured":"Woods D, Chen H-L, Goodfriend S, Dabby N, Winfree E, Yin P (2013) Active self-assembly of algorithmic shapes and patterns in polylogarithmic time. In: ITCS\u201913: Proceedings of the 4th conference on Innovations in Theoretical Computer Science. ACM, pp 353\u2013354. Full version: arXiv:1301.2626 [cs.DS]","DOI":"10.1145\/2422436.2422476"},{"key":"9432_CR53","doi-asserted-by":"crossref","first-page":"605","DOI":"10.1038\/35020524","volume":"406","author":"B Yurke","year":"2000","unstructured":"Yurke B, Turberfield AJ, Mills AP Jr, Simmel FC, Nuemann JL (2000) A DNA-fuelled molecular machine made of DNA. Nature 406:605\u2013608","journal-title":"Nature"}],"container-title":["Natural Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-014-9432-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11047-014-9432-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-014-9432-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,10]],"date-time":"2022-04-10T14:45:44Z","timestamp":1649601944000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11047-014-9432-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,7,6]]},"references-count":53,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,6]]}},"alternative-id":["9432"],"URL":"https:\/\/doi.org\/10.1007\/s11047-014-9432-y","relation":{},"ISSN":["1567-7818","1572-9796"],"issn-type":[{"value":"1567-7818","type":"print"},{"value":"1572-9796","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,7,6]]}}}