---
_id: '64259'
abstract:
- lang: eng
  text: Shape formation is one of the most thoroughly studied problems in programmable
    matter and swarm robotics. However, in many models, the class of shapes that can
    be formed is highly restricted due to the particles’ limited memory. In the hybrid
    model, an active agent with the computational power of a deterministic finite
    automaton can form shapes by lifting and placing passive tiles on the triangular
    lattice. We study the shape reconfiguration problem where the agent additionally
    has the ability to distinguish so-called target nodes from non-target nodes and
    needs to form a target shape from the initial tile configuration. We present a
    worst-case optimal O(mn) algorithm for simply connected target shapes, where m
    is the initial number of unoccupied target nodes and n is the total number of
    tiles. Furthermore, we show how an agent can reconfigure a large class of target
    shapes with holes in O(n^4) steps.
author:
- first_name: Jonas
  full_name: Friemel, Jonas
  last_name: Friemel
- first_name: David Jan
  full_name: Liedtke, David Jan
  id: '55557'
  last_name: Liedtke
- first_name: Christian
  full_name: Scheffer, Christian
  last_name: Scheffer
citation:
  ama: 'Friemel J, Liedtke DJ, Scheffer C. Tile Reconfiguration by a Finite Automaton.
    In: Di Giacomo E, Mondal D, eds. <i>WALCOM: Algorithms and Computation</i>. Springer
    Nature Singapore; 2026:512-526. doi:<a href="https://doi.org/10.1007/978-981-95-7127-7_34">10.1007/978-981-95-7127-7_34</a>'
  apa: 'Friemel, J., Liedtke, D. J., &#38; Scheffer, C. (2026). Tile Reconfiguration
    by a Finite Automaton. In E. Di Giacomo &#38; D. Mondal (Eds.), <i>WALCOM: Algorithms
    and Computation</i> (pp. 512–526). Springer Nature Singapore. <a href="https://doi.org/10.1007/978-981-95-7127-7_34">https://doi.org/10.1007/978-981-95-7127-7_34</a>'
  bibtex: '@inproceedings{Friemel_Liedtke_Scheffer_2026, place={Singapore}, title={Tile
    Reconfiguration by a Finite Automaton}, DOI={<a href="https://doi.org/10.1007/978-981-95-7127-7_34">10.1007/978-981-95-7127-7_34</a>},
    booktitle={WALCOM: Algorithms and Computation}, publisher={Springer Nature Singapore},
    author={Friemel, Jonas and Liedtke, David Jan and Scheffer, Christian}, editor={Di
    Giacomo, Emilio and Mondal, Debajyoti}, year={2026}, pages={512–526} }'
  chicago: 'Friemel, Jonas, David Jan Liedtke, and Christian Scheffer. “Tile Reconfiguration
    by a Finite Automaton.” In <i>WALCOM: Algorithms and Computation</i>, edited by
    Emilio Di Giacomo and Debajyoti Mondal, 512–26. Singapore: Springer Nature Singapore,
    2026. <a href="https://doi.org/10.1007/978-981-95-7127-7_34">https://doi.org/10.1007/978-981-95-7127-7_34</a>.'
  ieee: 'J. Friemel, D. J. Liedtke, and C. Scheffer, “Tile Reconfiguration by a Finite
    Automaton,” in <i>WALCOM: Algorithms and Computation</i>, Perugia, Italy, 2026,
    pp. 512–526, doi: <a href="https://doi.org/10.1007/978-981-95-7127-7_34">10.1007/978-981-95-7127-7_34</a>.'
  mla: 'Friemel, Jonas, et al. “Tile Reconfiguration by a Finite Automaton.” <i>WALCOM:
    Algorithms and Computation</i>, edited by Emilio Di Giacomo and Debajyoti Mondal,
    Springer Nature Singapore, 2026, pp. 512–26, doi:<a href="https://doi.org/10.1007/978-981-95-7127-7_34">10.1007/978-981-95-7127-7_34</a>.'
  short: 'J. Friemel, D.J. Liedtke, C. Scheffer, in: E. Di Giacomo, D. Mondal (Eds.),
    WALCOM: Algorithms and Computation, Springer Nature Singapore, Singapore, 2026,
    pp. 512–526.'
conference:
  end_date: 2026-03-06
  location: Perugia, Italy
  name: 20th International Conference and Workshops on Algorithms and Computation
    (WALCOM)
  start_date: 2026-03-04
date_created: 2026-02-19T10:57:30Z
date_updated: 2026-02-19T11:03:38Z
doi: 10.1007/978-981-95-7127-7_34
editor:
- first_name: Emilio
  full_name: Di Giacomo, Emilio
  last_name: Di Giacomo
- first_name: Debajyoti
  full_name: Mondal, Debajyoti
  last_name: Mondal
language:
- iso: eng
page: 512-526
place: Singapore
publication: 'WALCOM: Algorithms and Computation'
publication_identifier:
  isbn:
  - 978-981-95-7127-7
publication_status: published
publisher: Springer Nature Singapore
status: public
title: Tile Reconfiguration by a Finite Automaton
type: conference
user_id: '55557'
year: '2026'
...