---
_id: '55379'
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>'
author:
- first_name: Andreas
  full_name: Padalkin, Andreas
  id: '88238'
  last_name: Padalkin
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
- first_name: Daniel
  full_name: Warner, Daniel
  id: '3902'
  last_name: Warner
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>
  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>
  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}
    }'
  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>.
  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>.'
  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).
date_created: 2024-07-24T14:28:27Z
date_updated: 2024-07-24T14:28:43Z
doi: 10.1007/s11047-024-09981-6
language:
- iso: eng
publication: Natural Computing
publication_identifier:
  issn:
  - 1567-7818
  - 1572-9796
publication_status: published
publisher: Springer Science and Business Media LLC
status: public
title: The structural power of reconfigurable circuits in the amoebot model
type: journal_article
user_id: '88238'
year: '2024'
...
---
_id: '55376'
author:
- first_name: Andreas
  full_name: Padalkin, Andreas
  id: '88238'
  last_name: Padalkin
- first_name: Manish
  full_name: Kumar, Manish
  last_name: Kumar
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
citation:
  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>'
  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>
  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} }'
  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>.
  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>.'
  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>.
  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.'
date_created: 2024-07-24T14:25:07Z
date_updated: 2024-07-24T14:25:46Z
doi: 10.4230/LIPICS.SAND.2024.18
editor:
- first_name: Arnaud
  full_name: Casteigts, Arnaud
  last_name: Casteigts
- first_name: Fabian
  full_name: Kuhn, Fabian
  last_name: Kuhn
intvolume: '       292'
language:
- iso: eng
page: 18:1–18:20
publication: 3rd Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2024,
  June 5-7, 2024, Patras, Greece
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
series_title: LIPIcs
status: public
title: Reconfiguration and Locomotion with Joint Movements in the Amoebot Model
type: conference
user_id: '88238'
volume: 292
year: '2024'
...
---
_id: '55377'
author:
- first_name: Andreas
  full_name: Padalkin, Andreas
  id: '88238'
  last_name: Padalkin
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
citation:
  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>'
  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} }'
  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>.
  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>.'
  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>.
  short: 'A. Padalkin, C. Scheideler, in: Proceedings of the 43rd ACM Symposium on
    Principles of Distributed Computing, ACM, 2024.'
date_created: 2024-07-24T14:26:10Z
date_updated: 2024-07-24T14:26:23Z
doi: 10.1145/3662158.3662776
language:
- iso: eng
publication: Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing
publication_status: published
publisher: ACM
status: public
title: Polylogarithmic Time Algorithms for Shortest Path Forests in Programmable Matter
type: conference
user_id: '88238'
year: '2024'
...
---
_id: '31060'
author:
- first_name: Michael
  full_name: Feldmann, Michael
  last_name: Feldmann
- first_name: Andreas
  full_name: Padalkin, Andreas
  id: '88238'
  last_name: Padalkin
- first_name: Christian
  full_name: Scheideler, Christian
  id: '20792'
  last_name: Scheideler
- first_name: Shlomi
  full_name: Dolev, Shlomi
  last_name: Dolev
citation:
  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>
  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>
  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}
    }'
  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>.'
  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>.'
  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>.
  short: M. Feldmann, A. Padalkin, C. Scheideler, S. Dolev, J. Comput. Biol. 29 (2022)
    317–343.
date_created: 2022-05-04T12:29:22Z
date_updated: 2022-05-04T12:31:27Z
department:
- _id: '79'
doi: 10.1089/cmb.2021.0363
intvolume: '        29'
issue: '4'
language:
- iso: eng
page: 317–343
publication: J. Comput. Biol.
status: public
title: Coordinating Amoebots via Reconfigurable Circuits
type: journal_article
user_id: '15504'
volume: 29
year: '2022'
...