{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T11:08:56Z","timestamp":1740136136526,"version":"3.37.3"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2018,9,28]],"date-time":"2018-09-28T00:00:00Z","timestamp":1538092800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2018,9,28]],"date-time":"2018-09-28T00:00:00Z","timestamp":1538092800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-1422603","CCF-1637393","CCF-1733680","CCF-1526900","CCF-1637031","CCF-1733812"],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DGE-1148903"],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","award":["361047"],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Nat Comput"],"published-print":{"date-parts":[[2018,12]]},"DOI":"10.1007\/s11047-018-9714-x","type":"journal-article","created":{"date-parts":[[2018,9,28]],"date-time":"2018-09-28T11:50:05Z","timestamp":1538135405000},"page":"723-741","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["A stochastic approach to shortcut bridging in programmable matter"],"prefix":"10.1007","volume":"17","author":[{"given":"Marta","family":"Andr\u00e9s Arroyo","sequence":"first","affiliation":[]},{"given":"Sarah","family":"Cannon","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7294-5626","authenticated-orcid":false,"given":"Joshua J.","family":"Daymude","sequence":"additional","affiliation":[]},{"given":"Dana","family":"Randall","sequence":"additional","affiliation":[]},{"given":"Andr\u00e9a W.","family":"Richa","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,9,28]]},"reference":[{"key":"9714_CR1","doi-asserted-by":"crossref","unstructured":"Andr\u00e9s Arroyo M, Cannon S, Daymude JJ, Randall D, Richa AW (2017) A stochastic approach to shortcut bridging in programmable matter. In: DNA computing and molecular programming, DNA23, pp 122\u2013138","DOI":"10.1007\/978-3-319-66799-7_9"},{"issue":"4","key":"9714_CR2","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/s00446-005-0138-3","volume":"18","author":"D Angluin","year":"2006","unstructured":"Angluin D, Aspnes J, Diamadi Z, Fischer MJ, Peralta R (2006) Computation in networks of passively mobile finite-state sensors. Distrib Comput 18(4):235\u2013253","journal-title":"Distrib Comput"},{"key":"9714_CR3","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/BF01012867","volume":"22","author":"RJ Baxter","year":"1980","unstructured":"Baxter RJ, Enting IG, Tsang SK (1980) Hard-square lattice gas. J Stat Phys 22:465\u2013489","journal-title":"J Stat Phys"},{"key":"9714_CR4","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548318000238","author":"A Blanca","year":"2018","unstructured":"Blanca A, Chen Y, Galvin D, Randall D, Tetali P (2018) Phase coexistence for the hard-core model on $${\\mathbb{Z}}^2$$. Comb Prob Comput. \n https:\/\/doi.org\/10.1017\/S0963548318000238","journal-title":"Comb Prob Comput"},{"issue":"4","key":"9714_CR5","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1007\/s000400050156","volume":"46","author":"S Camazine","year":"1999","unstructured":"Camazine S, Visscher KP, Finley J, Vetter SR (1999) House-hunting by honey bee swarms: collective decisions and individual behaviors. Insectes Sociaux 46(4):348\u2013360","journal-title":"Insectes Sociaux"},{"key":"9714_CR6","doi-asserted-by":"crossref","unstructured":"Cannon S, Daymude JJ, Randall D, Richa AW (2016) A Markov chain algorithm for compression in self-organizing particle systems. In: Proceedings of the 2016 ACM symposium on principles of distributed computing, PODC\u201916, pp 279\u2013288","DOI":"10.1145\/2933057.2933107"},{"key":"9714_CR7","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1137\/1.9781611973068.47","volume-title":"Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Bernard Chazelle","year":"2009","unstructured":"Chazelle B (2009) Natural algorithms. In: Proceedings of the 20th ACM\u2013SIAM symposium on discrete algorithms, SODA\u201909, pp 422\u2013431"},{"issue":"2","key":"9714_CR8","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/s11047-014-9432-y","volume":"14","author":"M Chen","year":"2015","unstructured":"Chen M, Xin D, Woods D (2015) Parallel computation using active self-assembly. Nat Comput 14(2):225\u2013250","journal-title":"Nat Comput"},{"issue":"4","key":"9714_CR9","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1109\/TRO.2011.2132951","volume":"27","author":"KC Cheung","year":"2011","unstructured":"Cheung KC, Demaine ED, Bachrach JR, Griffith S (2011) Programmable assembly with universally foldable strings (moteins). IEEE Trans Robot 27(4):718\u2013729","journal-title":"IEEE Trans Robot"},{"key":"9714_CR10","doi-asserted-by":"crossref","unstructured":"Chirikjian GS (1994) Kinematics of a metamorphic robotic system. In: Proceedings of the 1994 IEEE international conference on robotics and automation, ICRA\u201994, vol 1, pp 449\u2013455","DOI":"10.1109\/ROBOT.1994.351256"},{"issue":"4","key":"9714_CR11","doi-asserted-by":"publisher","first-page":"829","DOI":"10.1137\/100796534","volume":"41","author":"M Cieliebak","year":"2012","unstructured":"Cieliebak M, Flocchini P, Prencipe G, Santoro N (2012) Distributed computing by mobile robots: gathering. SIAM J Comput 41(4):829\u2013879","journal-title":"SIAM J Comput"},{"key":"9714_CR12","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/978-3-319-72751-6_10","volume-title":"Algorithms for Sensor Systems","author":"Joshua J. Daymude","year":"2017","unstructured":"Daymude JJ, Gmyr R, Richa AW, Scheideler C, Strothmann T (2017a) Improved leader election for self-organizing programmable matter. In: Algorithms for sensor systems, ALGOSENSORS\u201917, pp 127\u2013140"},{"key":"9714_CR13","unstructured":"Daymude JJ, Richa AW, Scheideler C (2017b) The amoebot model. \n https:\/\/sops.engineering.asu.edu\/sops\/amoebot\n \n . Accessed 16 Sept 2018."},{"key":"9714_CR14","doi-asserted-by":"crossref","unstructured":"Derakhshandeh Z, Dolev S, Gmyr R, Richa AW, Scheideler C, Strothmann T (2014) Brief announcement: amoebot\u2014a new model for programmable matter. In: Proceedings of the 26th ACM symposium on parallelism in algorithms and architectures, SPAA\u201914, pp 220\u2013222","DOI":"10.1145\/2612669.2612712"},{"key":"9714_CR15","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/j.tcs.2016.02.039","volume":"671","author":"Z Derakhshandeh","year":"2017","unstructured":"Derakhshandeh Z, Gmyr R, Richa AW, Scheideler C, Strothmann T (2017) Universal coating for programmable matter. Theor Comput Sci 671:56\u201368","journal-title":"Theor Comput Sci"},{"key":"9714_CR16","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1038\/nature08016","volume":"459","author":"S Douglas","year":"2009","unstructured":"Douglas S, Dietz H, Liedl T, H\u00f6gberg B, Graf F, Shih W (2009) Self-assembly of DNA into nanoscale three-dimensional shapes. Nature 459:414\u2013418","journal-title":"Nature"},{"issue":"3","key":"9714_CR17","doi-asserted-by":"publisher","first-page":"1653","DOI":"10.4007\/annals.2012.175.3.14","volume":"275","author":"H Duminil-Copin","year":"2012","unstructured":"Duminil-Copin H, Smirnov S (2012) The connective constant of the honeycomb lattice equals $$\\sqrt{2+\\sqrt{2}}$$. Ann Math 275(3):1653\u20131665","journal-title":"Ann Math"},{"key":"9714_CR18","volume-title":"An introduction to probability theory and its applications","author":"W Feller","year":"1968","unstructured":"Feller W (1968) An introduction to probability theory and its applications, vol 1. Wiley, New York"},{"issue":"1","key":"9714_CR19","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1016\/j.tcs.2008.07.026","volume":"407","author":"P Flocchini","year":"2008","unstructured":"Flocchini P, Prencipe G, Santoro N, Widmayer P (2008) Arbitrary pattern formation by asynchronous, anonymous, oblivious robots. Theor Comput Sci 407(1):412\u2013447","journal-title":"Theor Comput Sci"},{"issue":"1","key":"9714_CR20","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1093\/biomet\/57.1.97","volume":"57","author":"WK Hastings","year":"1970","unstructured":"Hastings WK (1970) Monte carlo sampling methods using Markov chains and their applications. Biometrika 57(1):97\u2013109","journal-title":"Biometrika"},{"issue":"1","key":"9714_CR21","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/j.anbehav.2004.02.009","volume":"69","author":"R Jeanson","year":"2005","unstructured":"Jeanson R, Rivault C, Deneubourg J, Blanco S, Fournier R, Jost C, Theraulaz G (2005) Self-organized aggregation in cockroaches. Animal Behav 69(1):169\u2013180","journal-title":"Animal Behav"},{"key":"9714_CR22","volume-title":"Markov chains and mixing times","author":"DA Levin","year":"2009","unstructured":"Levin DA, Peres Y, Wilmer EL (2009) Markov chains and mixing times. American Mathematical Society, Providence"},{"key":"9714_CR23","volume-title":"Distributed algorithms","author":"N Lynch","year":"1996","unstructured":"Lynch N (1996) Distributed algorithms. Morgan Kauffman, Burlington"},{"key":"9714_CR24","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1038\/nnano.2016.277","volume":"12","author":"A Mohammed","year":"2017","unstructured":"Mohammed A, \u0160ulc P, Zenk J, Schulman R (2017) Self-assembling DNA nanotubes to connect molecular landmarks. Nat Nanotechnol 12:312\u2013316","journal-title":"Nat Nanotechnol"},{"issue":"6","key":"9714_CR25","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1093\/femsre\/fuw033","volume":"40","author":"CR Reid","year":"2016","unstructured":"Reid CR, Latty T (2016) Collective behaviour and swarm intelligence in slime moulds. FEMS Microbiol Rev 40(6):798\u2013806","journal-title":"FEMS Microbiol Rev"},{"issue":"49","key":"9714_CR26","doi-asserted-by":"publisher","first-page":"15113","DOI":"10.1073\/pnas.1512241112","volume":"112","author":"CR Reid","year":"2015","unstructured":"Reid CR, Lutz MJ, Powell S, Kao AB, Couzin ID, Garnier S (2015) Army ants dynamically adjust living bridges in response to a cost-benefit trade-off. Proc Natl Acad Sci 112(49):15113\u201315118","journal-title":"Proc Natl Acad Sci"},{"key":"9714_CR27","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/s00440-012-0421-8","volume":"156","author":"R Restrepo","year":"2013","unstructured":"Restrepo R, Shin J, Tetali P, Vigoda E, Yang L (2013) Improving mixing conditions on the grid for counting and sampling independent sets. Prob Theory Relat Fields 156:75\u201399","journal-title":"Prob Theory Relat Fields"},{"issue":"6198","key":"9714_CR28","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1126\/science.1254295","volume":"345","author":"M Rubenstein","year":"2014","unstructured":"Rubenstein M, Cornejo A, Nagpal R (2014) Programmable self-assembly in a thousand-robot swarm. Science 345(6198):795\u2013799","journal-title":"Science"},{"key":"9714_CR29","doi-asserted-by":"crossref","unstructured":"Walter JE, Brooks ME, Little DF, Amato NM (2004a) Enveloping multi-pocket obstacles with hexagonal metamorphic robots. In: Proceedings of the 2004 IEEE international conference on robotics and automation, ICRA\u201904, vol 3, pp 2204\u20132209","DOI":"10.1109\/ROBOT.2004.1307389"},{"issue":"2","key":"9714_CR30","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/s00446-003-0103-y","volume":"17","author":"JE Walter","year":"2004","unstructured":"Walter JE, Welch JL, Amato NM (2004b) Distributed reconfiguration of metamorphic robot chains. Distrib Comput 17(2):171\u2013189","journal-title":"Distrib Comput"},{"key":"9714_CR31","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1038\/nature11075","volume":"485","author":"B Wei","year":"2012","unstructured":"Wei B, Dai M, Yin P (2012) Complex shapes self-assembled from single-stranded DNA tiles. Nature 485:623\u2013626","journal-title":"Nature"},{"issue":"2046","key":"9714_CR32","doi-asserted-by":"publisher","first-page":"20140214","DOI":"10.1098\/rsta.2014.0214","volume":"373","author":"D Woods","year":"2015","unstructured":"Woods D (2015) Intrinsic universality and the computational power of self-assembly. Philos Trans R Soc A 373(2046):20140214","journal-title":"Philos Trans R Soc A"},{"key":"9714_CR33","doi-asserted-by":"crossref","unstructured":"Woods D, Chen HL, Goodfriend S, Dabby N, Winfree E, Yin P (2013) Active self-assembly of algorithmic shapes and patterns in polylogarithmic time. In: Proceedings of the 4th innovations in theoretical computer science conference, ITCS\u201913, pp 353\u2013354","DOI":"10.1145\/2422436.2422476"},{"issue":"1","key":"9714_CR34","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1109\/MRA.2007.339623","volume":"14","author":"M Yim","year":"2007","unstructured":"Yim M, Shen WM, Salemi B, Rus D, Moll M, Lipson H, Klavins E, Chirikjian GS (2007) Modular self-reconfigurable robot systems. IEEE Robot Autom Mag 14(1):43\u201352","journal-title":"IEEE Robot Autom Mag"}],"container-title":["Natural Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11047-018-9714-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-018-9714-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-018-9714-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,14]],"date-time":"2020-05-14T00:23:07Z","timestamp":1589415787000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11047-018-9714-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,28]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,12]]}},"alternative-id":["9714"],"URL":"https:\/\/doi.org\/10.1007\/s11047-018-9714-x","relation":{},"ISSN":["1567-7818","1572-9796"],"issn-type":[{"type":"print","value":"1567-7818"},{"type":"electronic","value":"1572-9796"}],"subject":[],"published":{"date-parts":[[2018,9,28]]},"assertion":[{"value":"28 September 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}