@article{55379,
  abstract     = {{<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>}},
  author       = {{Padalkin, Andreas and Scheideler, Christian and Warner, Daniel}},
  issn         = {{1567-7818}},
  journal      = {{Natural Computing}},
  publisher    = {{Springer Science and Business Media LLC}},
  title        = {{{The structural power of reconfigurable circuits in the amoebot model}}},
  doi          = {{10.1007/s11047-024-09981-6}},
  year         = {{2024}},
}

@inproceedings{55376,
  author       = {{Padalkin, Andreas and Kumar, Manish and Scheideler, Christian}},
  booktitle    = {{3rd Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2024, June 5-7, 2024, Patras, Greece}},
  editor       = {{Casteigts, Arnaud and Kuhn, Fabian}},
  pages        = {{18:1–18:20}},
  publisher    = {{Schloss Dagstuhl - Leibniz-Zentrum für Informatik}},
  title        = {{{Reconfiguration and Locomotion with Joint Movements in the Amoebot Model}}},
  doi          = {{10.4230/LIPICS.SAND.2024.18}},
  volume       = {{292}},
  year         = {{2024}},
}

@inproceedings{55377,
  author       = {{Padalkin, Andreas and Scheideler, Christian}},
  booktitle    = {{Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing}},
  publisher    = {{ACM}},
  title        = {{{Polylogarithmic Time Algorithms for Shortest Path Forests in Programmable Matter}}},
  doi          = {{10.1145/3662158.3662776}},
  year         = {{2024}},
}

@article{31060,
  author       = {{Feldmann, Michael and Padalkin, Andreas and Scheideler, Christian and Dolev, Shlomi}},
  journal      = {{J. Comput. Biol.}},
  number       = {{4}},
  pages        = {{317–343}},
  title        = {{{Coordinating Amoebots via Reconfigurable Circuits}}},
  doi          = {{10.1089/cmb.2021.0363}},
  volume       = {{29}},
  year         = {{2022}},
}