---
_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'
...