[{"_id":"55379","publisher":"Springer Science and Business Media LLC","language":[{"iso":"eng"}],"doi":"10.1007/s11047-024-09981-6","user_id":"88238","year":"2024","status":"public","title":"The structural power of reconfigurable circuits in the amoebot model","publication_identifier":{"issn":["1567-7818","1572-9796"]},"author":[{"id":"88238","last_name":"Padalkin","first_name":"Andreas","full_name":"Padalkin, Andreas"},{"full_name":"Scheideler, Christian","last_name":"Scheideler","first_name":"Christian","id":"20792"},{"full_name":"Warner, Daniel","last_name":"Warner","first_name":"Daniel","id":"3902"}],"date_updated":"2024-07-24T14:28:43Z","publication_status":"published","date_created":"2024-07-24T14:28:27Z","type":"journal_article","publication":"Natural Computing","citation":{"ama":"Padalkin A, Scheideler C, Warner D. The structural power of reconfigurable circuits in the amoebot model. <i>Natural Computing</i>. Published online 2024. doi:<a href=\"https://doi.org/10.1007/s11047-024-09981-6\">10.1007/s11047-024-09981-6</a>","bibtex":"@article{Padalkin_Scheideler_Warner_2024, title={The structural power of reconfigurable circuits in the amoebot model}, DOI={<a href=\"https://doi.org/10.1007/s11047-024-09981-6\">10.1007/s11047-024-09981-6</a>}, journal={Natural Computing}, publisher={Springer Science and Business Media LLC}, author={Padalkin, Andreas and Scheideler, Christian and Warner, Daniel}, year={2024} }","mla":"Padalkin, Andreas, et al. “The Structural Power of Reconfigurable Circuits in the Amoebot Model.” <i>Natural Computing</i>, Springer Science and Business Media LLC, 2024, doi:<a href=\"https://doi.org/10.1007/s11047-024-09981-6\">10.1007/s11047-024-09981-6</a>.","short":"A. Padalkin, C. Scheideler, D. Warner, Natural Computing (2024).","chicago":"Padalkin, Andreas, Christian Scheideler, and Daniel Warner. “The Structural Power of Reconfigurable Circuits in the Amoebot Model.” <i>Natural Computing</i>, 2024. <a href=\"https://doi.org/10.1007/s11047-024-09981-6\">https://doi.org/10.1007/s11047-024-09981-6</a>.","apa":"Padalkin, A., Scheideler, C., &#38; Warner, D. (2024). The structural power of reconfigurable circuits in the amoebot model. <i>Natural Computing</i>. <a href=\"https://doi.org/10.1007/s11047-024-09981-6\">https://doi.org/10.1007/s11047-024-09981-6</a>","ieee":"A. Padalkin, C. Scheideler, and D. Warner, “The structural power of reconfigurable circuits in the amoebot model,” <i>Natural Computing</i>, 2024, doi: <a href=\"https://doi.org/10.1007/s11047-024-09981-6\">10.1007/s11047-024-09981-6</a>."},"abstract":[{"lang":"eng","text":"<jats:title>Abstract</jats:title><jats:p>The <jats:italic>amoebot model</jats:italic> (Derakhshandeh et al. in: SPAA ACM, pp 220–222. <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–343. <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>"}]},{"publication":"3rd Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2024, June 5-7, 2024, Patras, Greece","citation":{"chicago":"Padalkin, Andreas, Manish Kumar, and Christian Scheideler. “Reconfiguration and Locomotion with Joint Movements in the Amoebot Model.” In <i>3rd Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2024, June 5-7, 2024, Patras, Greece</i>, edited by Arnaud Casteigts and Fabian Kuhn, 292:18:1–18:20. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPICS.SAND.2024.18\">https://doi.org/10.4230/LIPICS.SAND.2024.18</a>.","short":"A. Padalkin, M. Kumar, C. Scheideler, in: A. Casteigts, F. Kuhn (Eds.), 3rd Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2024, June 5-7, 2024, Patras, Greece, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, p. 18:1–18:20.","apa":"Padalkin, A., Kumar, M., &#38; Scheideler, C. (2024). Reconfiguration and Locomotion with Joint Movements in the Amoebot Model. In A. Casteigts &#38; F. Kuhn (Eds.), <i>3rd Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2024, June 5-7, 2024, Patras, Greece</i> (Vol. 292, p. 18:1–18:20). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.SAND.2024.18\">https://doi.org/10.4230/LIPICS.SAND.2024.18</a>","ieee":"A. Padalkin, M. Kumar, and C. Scheideler, “Reconfiguration and Locomotion with Joint Movements in the Amoebot Model,” in <i>3rd Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2024, June 5-7, 2024, Patras, Greece</i>, 2024, vol. 292, p. 18:1–18:20, doi: <a href=\"https://doi.org/10.4230/LIPICS.SAND.2024.18\">10.4230/LIPICS.SAND.2024.18</a>.","ama":"Padalkin A, Kumar M, Scheideler C. Reconfiguration and Locomotion with Joint Movements in the Amoebot Model. In: Casteigts A, Kuhn F, eds. <i>3rd Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2024, June 5-7, 2024, Patras, Greece</i>. Vol 292. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024:18:1–18:20. doi:<a href=\"https://doi.org/10.4230/LIPICS.SAND.2024.18\">10.4230/LIPICS.SAND.2024.18</a>","bibtex":"@inproceedings{Padalkin_Kumar_Scheideler_2024, series={LIPIcs}, title={Reconfiguration and Locomotion with Joint Movements in the Amoebot Model}, volume={292}, DOI={<a href=\"https://doi.org/10.4230/LIPICS.SAND.2024.18\">10.4230/LIPICS.SAND.2024.18</a>}, booktitle={3rd Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2024, June 5-7, 2024, Patras, Greece}, publisher={Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, author={Padalkin, Andreas and Kumar, Manish and Scheideler, Christian}, editor={Casteigts, Arnaud and Kuhn, Fabian}, year={2024}, pages={18:1–18:20}, collection={LIPIcs} }","mla":"Padalkin, Andreas, et al. “Reconfiguration and Locomotion with Joint Movements in the Amoebot Model.” <i>3rd Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2024, June 5-7, 2024, Patras, Greece</i>, edited by Arnaud Casteigts and Fabian Kuhn, vol. 292, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, p. 18:1–18:20, doi:<a href=\"https://doi.org/10.4230/LIPICS.SAND.2024.18\">10.4230/LIPICS.SAND.2024.18</a>."},"type":"conference","date_created":"2024-07-24T14:25:07Z","date_updated":"2024-07-24T14:25:46Z","intvolume":"       292","status":"public","title":"Reconfiguration and Locomotion with Joint Movements in the Amoebot Model","year":"2024","author":[{"full_name":"Padalkin, Andreas","last_name":"Padalkin","first_name":"Andreas","id":"88238"},{"last_name":"Kumar","first_name":"Manish","full_name":"Kumar, Manish"},{"full_name":"Scheideler, Christian","first_name":"Christian","last_name":"Scheideler","id":"20792"}],"doi":"10.4230/LIPICS.SAND.2024.18","user_id":"88238","editor":[{"full_name":"Casteigts, Arnaud","first_name":"Arnaud","last_name":"Casteigts"},{"last_name":"Kuhn","first_name":"Fabian","full_name":"Kuhn, Fabian"}],"volume":292,"page":"18:1–18:20","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","_id":"55376","language":[{"iso":"eng"}],"series_title":"LIPIcs"},{"status":"public","year":"2024","title":"Polylogarithmic Time Algorithms for Shortest Path Forests in Programmable Matter","author":[{"id":"88238","full_name":"Padalkin, Andreas","first_name":"Andreas","last_name":"Padalkin"},{"full_name":"Scheideler, Christian","first_name":"Christian","last_name":"Scheideler","id":"20792"}],"date_updated":"2024-07-24T14:26:23Z","publication_status":"published","_id":"55377","publisher":"ACM","language":[{"iso":"eng"}],"doi":"10.1145/3662158.3662776","user_id":"88238","publication":"Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing","citation":{"chicago":"Padalkin, Andreas, and Christian Scheideler. “Polylogarithmic Time Algorithms for Shortest Path Forests in Programmable Matter.” In <i>Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing</i>. ACM, 2024. <a href=\"https://doi.org/10.1145/3662158.3662776\">https://doi.org/10.1145/3662158.3662776</a>.","short":"A. Padalkin, C. Scheideler, in: Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing, ACM, 2024.","ieee":"A. Padalkin and C. Scheideler, “Polylogarithmic Time Algorithms for Shortest Path Forests in Programmable Matter,” 2024, doi: <a href=\"https://doi.org/10.1145/3662158.3662776\">10.1145/3662158.3662776</a>.","apa":"Padalkin, A., &#38; Scheideler, C. (2024). Polylogarithmic Time Algorithms for Shortest Path Forests in Programmable Matter. <i>Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing</i>. <a href=\"https://doi.org/10.1145/3662158.3662776\">https://doi.org/10.1145/3662158.3662776</a>","bibtex":"@inproceedings{Padalkin_Scheideler_2024, title={Polylogarithmic Time Algorithms for Shortest Path Forests in Programmable Matter}, DOI={<a href=\"https://doi.org/10.1145/3662158.3662776\">10.1145/3662158.3662776</a>}, booktitle={Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing}, publisher={ACM}, author={Padalkin, Andreas and Scheideler, Christian}, year={2024} }","ama":"Padalkin A, Scheideler C. Polylogarithmic Time Algorithms for Shortest Path Forests in Programmable Matter. In: <i>Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing</i>. ACM; 2024. doi:<a href=\"https://doi.org/10.1145/3662158.3662776\">10.1145/3662158.3662776</a>","mla":"Padalkin, Andreas, and Christian Scheideler. “Polylogarithmic Time Algorithms for Shortest Path Forests in Programmable Matter.” <i>Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing</i>, ACM, 2024, doi:<a href=\"https://doi.org/10.1145/3662158.3662776\">10.1145/3662158.3662776</a>."},"date_created":"2024-07-24T14:26:10Z","type":"conference"},{"publication":"J. Comput. Biol.","issue":"4","citation":{"ieee":"M. Feldmann, A. Padalkin, C. Scheideler, and S. Dolev, “Coordinating Amoebots via Reconfigurable Circuits,” <i>J. Comput. Biol.</i>, vol. 29, no. 4, pp. 317–343, 2022, doi: <a href=\"https://doi.org/10.1089/cmb.2021.0363\">10.1089/cmb.2021.0363</a>.","apa":"Feldmann, M., Padalkin, A., Scheideler, C., &#38; Dolev, S. (2022). Coordinating Amoebots via Reconfigurable Circuits. <i>J. Comput. Biol.</i>, <i>29</i>(4), 317–343. <a href=\"https://doi.org/10.1089/cmb.2021.0363\">https://doi.org/10.1089/cmb.2021.0363</a>","short":"M. Feldmann, A. Padalkin, C. Scheideler, S. Dolev, J. Comput. Biol. 29 (2022) 317–343.","chicago":"Feldmann, Michael, Andreas Padalkin, Christian Scheideler, and Shlomi Dolev. “Coordinating Amoebots via Reconfigurable Circuits.” <i>J. Comput. Biol.</i> 29, no. 4 (2022): 317–343. <a href=\"https://doi.org/10.1089/cmb.2021.0363\">https://doi.org/10.1089/cmb.2021.0363</a>.","mla":"Feldmann, Michael, et al. “Coordinating Amoebots via Reconfigurable Circuits.” <i>J. Comput. Biol.</i>, vol. 29, no. 4, 2022, pp. 317–343, doi:<a href=\"https://doi.org/10.1089/cmb.2021.0363\">10.1089/cmb.2021.0363</a>.","bibtex":"@article{Feldmann_Padalkin_Scheideler_Dolev_2022, title={Coordinating Amoebots via Reconfigurable Circuits}, volume={29}, DOI={<a href=\"https://doi.org/10.1089/cmb.2021.0363\">10.1089/cmb.2021.0363</a>}, number={4}, journal={J. Comput. Biol.}, author={Feldmann, Michael and Padalkin, Andreas and Scheideler, Christian and Dolev, Shlomi}, year={2022}, pages={317–343} }","ama":"Feldmann M, Padalkin A, Scheideler C, Dolev S. Coordinating Amoebots via Reconfigurable Circuits. <i>J Comput Biol</i>. 2022;29(4):317–343. doi:<a href=\"https://doi.org/10.1089/cmb.2021.0363\">10.1089/cmb.2021.0363</a>"},"type":"journal_article","department":[{"_id":"79"}],"date_created":"2022-05-04T12:29:22Z","date_updated":"2022-05-04T12:31:27Z","intvolume":"        29","title":"Coordinating Amoebots via Reconfigurable Circuits","status":"public","year":"2022","author":[{"last_name":"Feldmann","first_name":"Michael","full_name":"Feldmann, Michael"},{"id":"88238","last_name":"Padalkin","first_name":"Andreas","full_name":"Padalkin, Andreas"},{"id":"20792","last_name":"Scheideler","first_name":"Christian","full_name":"Scheideler, Christian"},{"last_name":"Dolev","first_name":"Shlomi","full_name":"Dolev, Shlomi"}],"doi":"10.1089/cmb.2021.0363","user_id":"15504","volume":29,"page":"317–343","language":[{"iso":"eng"}],"_id":"31060"}]