{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,18]],"date-time":"2026-04-18T14:27:16Z","timestamp":1776522436222,"version":"3.51.2"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2024,4,13]],"date-time":"2024-04-13T00:00:00Z","timestamp":1712966400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,4,13]],"date-time":"2024-04-13T00:00:00Z","timestamp":1712966400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["Project SCHE 1592\/6-1 (PROG-MATTER)"],"award-info":[{"award-number":["Project SCHE 1592\/6-1 (PROG-MATTER)"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["Project SCHE 1592\/6-1 (PROG-MATTER)"],"award-info":[{"award-number":["Project SCHE 1592\/6-1 (PROG-MATTER)"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100008007","name":"Universit\u00e4t Paderborn","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100008007","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Nat Comput"],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The <jats:italic>amoebot model<\/jats:italic> (Derakhshandeh et al. in: SPAA ACM, pp 220\u2013222. <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"doi\" xlink:href=\"10.1145\/2612669.2612712\">https:\/\/doi.org\/10.1145\/2612669.2612712<\/jats:ext-link>, 2014) has been proposed as a model for programmable matter consisting of tiny, robotic elements called <jats:italic>amoebots<\/jats:italic>. We consider the <jats:italic>reconfigurable circuit extension<\/jats:italic> (Feldmann et al. in J Comput Biol 29(4):317\u2013343. <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"doi\" xlink:href=\"10.1089\/cmb.2021.0363\">https:\/\/doi.org\/10.1089\/cmb.2021.0363<\/jats:ext-link>, 2022) of the geometric amoebot model that allows the amoebot structure to interconnect amoebots by so-called <jats:italic>circuits<\/jats:italic>. A circuit permits the instantaneous transmission of signals between the connected amoebots. In this paper, we examine the structural power of the reconfigurable circuits. We start with fundamental problems like the <jats:italic>stripe computation problem<\/jats:italic> where, given any connected amoebot structure <jats:italic>S<\/jats:italic>, an amoebot <jats:italic>u<\/jats:italic> in <jats:italic>S<\/jats:italic>, and some axis <jats:italic>X<\/jats:italic>, all amoebots belonging to axis <jats:italic>X<\/jats:italic> through <jats:italic>u<\/jats:italic> have to be identified. Second, we consider the <jats:italic>global maximum problem<\/jats:italic>, which identifies an amoebot at the highest possible position with respect to some direction in some given amoebot (sub)structure. A solution to this problem can be used to solve the <jats:italic>skeleton problem<\/jats:italic>, where a cycle of amoebots has to be found in the given amoebot structure which contains all boundary amoebots. A canonical solution to that problem can be used to come up with a canonical path, which provides a unique characterization of the shape of the given amoebot structure. Constructing canonical paths for different directions allows the amoebots to set up a spanning tree and to check symmetry properties of the given amoebot structure. The problems are important for a number of applications like rapid shape transformation, energy dissemination, and structural monitoring. Interestingly, the reconfigurable circuit extension allows polylogarithmic-time solutions to all of these problems.<\/jats:p>","DOI":"10.1007\/s11047-024-09981-6","type":"journal-article","created":{"date-parts":[[2024,4,13]],"date-time":"2024-04-13T06:01:45Z","timestamp":1712988105000},"page":"603-625","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["The structural power of reconfigurable circuits in the amoebot model"],"prefix":"10.1007","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4601-9597","authenticated-orcid":false,"given":"Andreas","family":"Padalkin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5278-528X","authenticated-orcid":false,"given":"Christian","family":"Scheideler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9423-6094","authenticated-orcid":false,"given":"Daniel","family":"Warner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,4,13]]},"reference":[{"key":"9981_CR1","doi-asserted-by":"publisher","unstructured":"Alumbaugh JC, Daymude JJ, Demaine ED, et\u00a0al (2019) Simulation of programmable matter systems using active tile-based self-assembly. In: DNA, lecture notes in computer science, vol 11648. Springer, pp 140\u2013158. https:\/\/doi.org\/10.1007\/978-3-030-26807-7_8","DOI":"10.1007\/978-3-030-26807-7_8"},{"issue":"4","key":"9981_CR2","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1007\/s11047-018-9714-x","volume":"17","author":"MA Arroyo","year":"2018","unstructured":"Arroyo MA, Cannon S, Daymude JJ et al (2018) A stochastic approach to shortcut bridging in programmable matter. Nat Comput 17(4):723\u2013741","journal-title":"Nat Comput"},{"key":"9981_CR3","doi-asserted-by":"crossref","unstructured":"Cannon S, Daymude JJ, Randall D, et\u00a0al (2016) A markov chain algorithm for compression in self-organizing particle systems. In: PODC. ACM, pp 279\u2013288","DOI":"10.1145\/2933057.2933107"},{"key":"9981_CR4","doi-asserted-by":"publisher","unstructured":"Daymude JJ, Hinnenthal K, Richa AW, et\u00a0al (2019) Computing by programmable particles. In: Distributed computing by mobile entities, lecture notes in computer science, vol 11340. Springer, pp 615\u2013681, https:\/\/doi.org\/10.1007\/978-3-030-11072-7_22","DOI":"10.1007\/978-3-030-11072-7_22"},{"key":"9981_CR5","doi-asserted-by":"publisher","unstructured":"Daymude JJ, Gmyr R, Hinnenthal K, et\u00a0al (2020) Convex hull formation for programmable matter. In: ICDCN. ACM, pp 2:1\u20132:10, https:\/\/doi.org\/10.1145\/3369740.3372916","DOI":"10.1145\/3369740.3372916"},{"key":"9981_CR6","doi-asserted-by":"publisher","unstructured":"Daymude JJ, Richa AW, Weber JW (2021) Bio-inspired energy distribution for programmable matter. In: ICDCN. ACM, pp 86\u201395. https:\/\/doi.org\/10.1145\/3427796.3427835","DOI":"10.1145\/3427796.3427835"},{"issue":"2","key":"9981_CR7","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/s00446-023-00443-3","volume":"36","author":"JJ Daymude","year":"2023","unstructured":"Daymude JJ, Richa AW, Scheideler C (2023) The canonical amoebot model: algorithms and concurrency control. Distributed Comput 36(2):159\u2013192","journal-title":"Distributed Comput"},{"key":"9981_CR8","doi-asserted-by":"publisher","unstructured":"Derakhshandeh Z, Dolev S, Gmyr R, et\u00a0al (2014) Brief announcement: amoebot - a new model for programmable matter. In: SPAA. ACM, pp 220\u2013222, https:\/\/doi.org\/10.1145\/2612669.2612712","DOI":"10.1145\/2612669.2612712"},{"key":"9981_CR9","doi-asserted-by":"publisher","unstructured":"Derakhshandeh Z, Gmyr R, Strothmann T, et\u00a0al (2015) Leader election and shape formation with self-organizing programmable matter. In: DNA, Lecture Notes in Computer Science, vol 9211. Springer, pp 117\u2013132, https:\/\/doi.org\/10.1007\/978-3-319-21999-8_8","DOI":"10.1007\/978-3-319-21999-8_8"},{"key":"9981_CR10","doi-asserted-by":"publisher","unstructured":"Derakhshandeh Z, Gmyr R, Richa AW, et\u00a0al (2016) Universal shape formation for programmable matter. In: SPAA. ACM, pp 289\u2013299. https:\/\/doi.org\/10.1145\/2935764.2935784","DOI":"10.1145\/2935764.2935784"},{"key":"9981_CR11","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 et al (2017) Universal coating for programmable matter. Theor Comput Sci 671:56\u201368. https:\/\/doi.org\/10.1016\/j.tcs.2016.02.039","journal-title":"Theor Comput Sci"},{"issue":"4","key":"9981_CR12","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1089\/cmb.2021.0363","volume":"29","author":"M Feldmann","year":"2022","unstructured":"Feldmann M, Padalkin A, Scheideler C et al (2022) Coordinating amoebots via reconfigurable circuits. J Comput Biol 29(4):317\u2013343. https:\/\/doi.org\/10.1089\/cmb.2021.0363","journal-title":"J Comput Biol"},{"issue":"1","key":"9981_CR13","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/s00446-019-00350-6","volume":"33","author":"GAD Luna","year":"2020","unstructured":"Luna GAD, Flocchini P, Santoro N et al (2020) Shape formation by programmable particles. Distributed Comput 33(1):69\u2013101. https:\/\/doi.org\/10.1007\/s00446-019-00350-6","journal-title":"Distributed Comput"},{"issue":"20","key":"9981_CR14","doi-asserted-by":"publisher","first-page":"5939","DOI":"10.1002\/ange.201500252","volume":"54","author":"JE Padilla","year":"2015","unstructured":"Padilla JE, Sha R, Kristiansen M et al (2015) A signal-passing dna-strand-exchange mechanism for active self-assembly of dna nanostructures. Angew Chem Int Ed 54(20):5939\u20135942. https:\/\/doi.org\/10.1002\/ange.201500252","journal-title":"Angew Chem Int Ed"},{"key":"9981_CR15","unstructured":"Pandurangan G, Robinson P, Scquizzato M (2018) The distributed minimum spanning tree problem. Bull EATCS 125"},{"issue":"1","key":"9981_CR16","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1146\/annurev-bioeng-060418-052357","volume":"21","author":"D Scalise","year":"2019","unstructured":"Scalise D, Schulman R (2019) Controlling matter at the molecular scale with dna circuits. Annu Rev Biomed Eng 21(1):469\u2013493. https:\/\/doi.org\/10.1146\/annurev-bioeng-060418-052357","journal-title":"Annu Rev Biomed Eng"},{"issue":"21","key":"9981_CR17","doi-asserted-by":"publisher","first-page":"9587","DOI":"10.1021\/jacs.0c02240","volume":"142","author":"S Shah","year":"2020","unstructured":"Shah S, Wee J, Song T et al (2020) Using strand displacing polymerase to program chemical reaction networks. J Am Chem Soc 142(21):9587\u20139593. https:\/\/doi.org\/10.1021\/jacs.0c02240","journal-title":"J Am Chem Soc"},{"issue":"11","key":"9981_CR18","doi-asserted-by":"publisher","first-page":"1075","DOI":"10.1038\/s41565-019-0544-5","volume":"14","author":"T Song","year":"2019","unstructured":"Song T, Eshra A, Shah S et al (2019) Fast and compact dna logic circuits based on single-stranded gates using strand-displacing polymerase. Nat Nanotechnol 14(11):1075\u20131081. https:\/\/doi.org\/10.1038\/s41565-019-0544-5","journal-title":"Nat Nanotechnol"},{"issue":"2","key":"9981_CR19","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1142\/S0129053393000086","volume":"5","author":"T Toffoli","year":"1993","unstructured":"Toffoli T, Margolus N (1993) Programmable matter: Concepts and realization. Int J High Speed Comput 5(2):155\u2013170. https:\/\/doi.org\/10.1142\/S0129053393000086","journal-title":"Int J High Speed Comput"}],"container-title":["Natural Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-024-09981-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11047-024-09981-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-024-09981-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,25]],"date-time":"2024-11-25T18:14:29Z","timestamp":1732558469000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11047-024-09981-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,13]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["9981"],"URL":"https:\/\/doi.org\/10.1007\/s11047-024-09981-6","relation":{},"ISSN":["1567-7818","1572-9796"],"issn-type":[{"value":"1567-7818","type":"print"},{"value":"1572-9796","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,13]]},"assertion":[{"value":"29 February 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 April 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical Approval"}}]}}