[{"publication_status":"published","publication_identifier":{"isbn":["978-981-95-7127-7"]},"citation":{"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} }","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.","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>","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>","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>.","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>."},"page":"512-526","year":"2026","place":"Singapore","date_created":"2026-02-19T10:57:30Z","author":[{"first_name":"Jonas","last_name":"Friemel","full_name":"Friemel, Jonas"},{"first_name":"David Jan","id":"55557","full_name":"Liedtke, David Jan","last_name":"Liedtke"},{"first_name":"Christian","full_name":"Scheffer, Christian","last_name":"Scheffer"}],"publisher":"Springer Nature Singapore","date_updated":"2026-02-19T11:03:38Z","doi":"10.1007/978-981-95-7127-7_34","conference":{"start_date":"2026-03-04","name":"20th International Conference and Workshops on Algorithms and Computation (WALCOM)","location":"Perugia, Italy","end_date":"2026-03-06"},"title":"Tile Reconfiguration by a Finite Automaton","type":"conference","publication":"WALCOM: Algorithms and Computation","status":"public","abstract":[{"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.","lang":"eng"}],"editor":[{"full_name":"Di Giacomo, Emilio","last_name":"Di Giacomo","first_name":"Emilio"},{"first_name":"Debajyoti","last_name":"Mondal","full_name":"Mondal, Debajyoti"}],"user_id":"55557","_id":"64259","language":[{"iso":"eng"}]},{"_id":"62285","department":[{"_id":"79"}],"user_id":"15578","editor":[{"full_name":"Bonomi, Silvia","last_name":"Bonomi","first_name":"Silvia"},{"last_name":"Mandal","full_name":"Mandal, Partha Sarathi","first_name":"Partha Sarathi"},{"full_name":"Robinson, Peter","last_name":"Robinson","first_name":"Peter"},{"full_name":"Sharma, Gokarna","last_name":"Sharma","first_name":"Gokarna"},{"full_name":"Tixeuil, Sebastien","last_name":"Tixeuil","first_name":"Sebastien"}],"status":"public","type":"conference","conference":{"start_date":"2025-10-09","name":"27th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)","location":"Kathmandu","end_date":"2025-10-11"},"doi":"10.1007/978-3-032-11127-2_26","date_updated":"2026-02-11T08:31:14Z","author":[{"last_name":"Kostitsyna","full_name":"Kostitsyna, Irina","first_name":"Irina"},{"first_name":"David Jan","id":"55557","full_name":"Liedtke, David Jan","last_name":"Liedtke"},{"full_name":"Scheideler, Christian","id":"20792","last_name":"Scheideler","first_name":"Christian"}],"place":"Cham","page":"325-342","citation":{"ieee":"I. Kostitsyna, D. J. Liedtke, and C. Scheideler, “Invited Paper: Distributed Rhombus Formation of Sliding Squares,” in <i>Stabilization, Safety, and Security of Distributed Systems</i>, Kathmandu, 2025, pp. 325–342, doi: <a href=\"https://doi.org/10.1007/978-3-032-11127-2_26\">10.1007/978-3-032-11127-2_26</a>.","chicago":"Kostitsyna, Irina, David Jan Liedtke, and Christian Scheideler. “Invited Paper: Distributed Rhombus Formation of Sliding Squares.” In <i>Stabilization, Safety, and Security of Distributed Systems</i>, edited by Silvia Bonomi, Partha Sarathi Mandal, Peter Robinson, Gokarna Sharma, and Sebastien Tixeuil, 325–42. Cham: Springer Nature Switzerland, 2025. <a href=\"https://doi.org/10.1007/978-3-032-11127-2_26\">https://doi.org/10.1007/978-3-032-11127-2_26</a>.","ama":"Kostitsyna I, Liedtke DJ, Scheideler C. Invited Paper: Distributed Rhombus Formation of Sliding Squares. In: Bonomi S, Mandal PS, Robinson P, Sharma G, Tixeuil S, eds. <i>Stabilization, Safety, and Security of Distributed Systems</i>. Springer Nature Switzerland; 2025:325-342. doi:<a href=\"https://doi.org/10.1007/978-3-032-11127-2_26\">10.1007/978-3-032-11127-2_26</a>","apa":"Kostitsyna, I., Liedtke, D. J., &#38; Scheideler, C. (2025). Invited Paper: Distributed Rhombus Formation of Sliding Squares. In S. Bonomi, P. S. Mandal, P. Robinson, G. Sharma, &#38; S. Tixeuil (Eds.), <i>Stabilization, Safety, and Security of Distributed Systems</i> (pp. 325–342). Springer Nature Switzerland. <a href=\"https://doi.org/10.1007/978-3-032-11127-2_26\">https://doi.org/10.1007/978-3-032-11127-2_26</a>","bibtex":"@inproceedings{Kostitsyna_Liedtke_Scheideler_2025, place={Cham}, title={Invited Paper: Distributed Rhombus Formation of Sliding Squares}, DOI={<a href=\"https://doi.org/10.1007/978-3-032-11127-2_26\">10.1007/978-3-032-11127-2_26</a>}, booktitle={Stabilization, Safety, and Security of Distributed Systems}, publisher={Springer Nature Switzerland}, author={Kostitsyna, Irina and Liedtke, David Jan and Scheideler, Christian}, editor={Bonomi, Silvia and Mandal, Partha Sarathi and Robinson, Peter and Sharma, Gokarna and Tixeuil, Sebastien}, year={2025}, pages={325–342} }","short":"I. Kostitsyna, D.J. Liedtke, C. Scheideler, in: S. Bonomi, P.S. Mandal, P. Robinson, G. Sharma, S. Tixeuil (Eds.), Stabilization, Safety, and Security of Distributed Systems, Springer Nature Switzerland, Cham, 2025, pp. 325–342.","mla":"Kostitsyna, Irina, et al. “Invited Paper: Distributed Rhombus Formation of Sliding Squares.” <i>Stabilization, Safety, and Security of Distributed Systems</i>, edited by Silvia Bonomi et al., Springer Nature Switzerland, 2025, pp. 325–42, doi:<a href=\"https://doi.org/10.1007/978-3-032-11127-2_26\">10.1007/978-3-032-11127-2_26</a>."},"publication_identifier":{"issn":["0302-9743","1611-3349"],"isbn":["9783032111265","9783032111272"]},"publication_status":"published","language":[{"iso":"eng"}],"abstract":[{"lang":"eng","text":"The sliding square model is a widely used abstraction for studying self-reconfigurable robotic systems, where modules are square-shaped robots that move by sliding or rotating over one another. In this paper, we propose a novel distributed algorithm that enables a group of modules to reconfigure into a rhombus shape, starting from an arbitrary side-connected configuration. It is connectivity-preserving and operates under minimal assumptions: one leader module, common chirality, constant memory per module, and visibility and communication restricted to immediate neighbors. Unlike prior work, which relaxes the original sliding square move-set, our approach uses the unmodified move-set, addressing the additional challenge of handling locked configurations. Our algorithm is sequential in nature and operates with a worst-case time complexity of O(n^2) rounds, which is optimal for sequential algorithms. To improve runtime, we introduce two parallel variants of the algorithm. Both rely on a spanning tree data structure, allowing modules to make decisions based on local connectivity. Our experimental results show a significant speedup for the first variant, and a linear average runtime for the second variant, which is worst-case optimal for parallel algorithms."}],"publication":"Stabilization, Safety, and Security of Distributed Systems","title":"Invited Paper: Distributed Rhombus Formation of Sliding Squares","publisher":"Springer Nature Switzerland","date_created":"2025-11-23T21:07:12Z","year":"2025"},{"status":"public","type":"journal_article","publication":"Theoretical Computer Science","article_number":"115552","language":[{"iso":"eng"}],"_id":"62051","user_id":"55557","department":[{"_id":"79"}],"year":"2025","citation":{"apa":"Hinnenthal, K., Liedtke, D. J., &#38; Scheideler, C. (2025). Efficient shape formation by 3D hybrid programmable matter: An algorithm for low diameter intermediate structures. <i>Theoretical Computer Science</i>, <i>1057</i>, Article 115552. <a href=\"https://doi.org/10.1016/j.tcs.2025.115552\">https://doi.org/10.1016/j.tcs.2025.115552</a>","short":"K. Hinnenthal, D.J. Liedtke, C. Scheideler, Theoretical Computer Science 1057 (2025).","mla":"Hinnenthal, Kristian, et al. “Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures.” <i>Theoretical Computer Science</i>, vol. 1057, 115552, Elsevier BV, 2025, doi:<a href=\"https://doi.org/10.1016/j.tcs.2025.115552\">10.1016/j.tcs.2025.115552</a>.","bibtex":"@article{Hinnenthal_Liedtke_Scheideler_2025, title={Efficient shape formation by 3D hybrid programmable matter: An algorithm for low diameter intermediate structures}, volume={1057}, DOI={<a href=\"https://doi.org/10.1016/j.tcs.2025.115552\">10.1016/j.tcs.2025.115552</a>}, number={115552}, journal={Theoretical Computer Science}, publisher={Elsevier BV}, author={Hinnenthal, Kristian and Liedtke, David Jan and Scheideler, Christian}, year={2025} }","ieee":"K. Hinnenthal, D. J. Liedtke, and C. Scheideler, “Efficient shape formation by 3D hybrid programmable matter: An algorithm for low diameter intermediate structures,” <i>Theoretical Computer Science</i>, vol. 1057, Art. no. 115552, 2025, doi: <a href=\"https://doi.org/10.1016/j.tcs.2025.115552\">10.1016/j.tcs.2025.115552</a>.","chicago":"Hinnenthal, Kristian, David Jan Liedtke, and Christian Scheideler. “Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures.” <i>Theoretical Computer Science</i> 1057 (2025). <a href=\"https://doi.org/10.1016/j.tcs.2025.115552\">https://doi.org/10.1016/j.tcs.2025.115552</a>.","ama":"Hinnenthal K, Liedtke DJ, Scheideler C. Efficient shape formation by 3D hybrid programmable matter: An algorithm for low diameter intermediate structures. <i>Theoretical Computer Science</i>. 2025;1057. doi:<a href=\"https://doi.org/10.1016/j.tcs.2025.115552\">10.1016/j.tcs.2025.115552</a>"},"intvolume":"      1057","publication_status":"published","publication_identifier":{"issn":["0304-3975"]},"title":"Efficient shape formation by 3D hybrid programmable matter: An algorithm for low diameter intermediate structures","doi":"10.1016/j.tcs.2025.115552","publisher":"Elsevier BV","date_updated":"2025-11-03T10:21:52Z","date_created":"2025-11-03T10:19:53Z","author":[{"first_name":"Kristian","last_name":"Hinnenthal","full_name":"Hinnenthal, Kristian","id":"32229"},{"last_name":"Liedtke","full_name":"Liedtke, David Jan","id":"55557","first_name":"David Jan"},{"id":"20792","full_name":"Scheideler, Christian","last_name":"Scheideler","first_name":"Christian"}],"volume":1057},{"type":"conference","publication":"3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)","editor":[{"last_name":"Casteigts","full_name":"Casteigts, Arnaud","first_name":"Arnaud"},{"last_name":"Kuhn","full_name":"Kuhn, Fabian","first_name":"Fabian"}],"abstract":[{"text":"This paper considers the shape formation problem within the 3D hybrid model, where a single agent with a strictly limited viewing range and the computational capacity of a deterministic finite automaton manipulates passive tiles through pick-up, movement, and placement actions. The goal is to reconfigure a set of tiles into a specific shape termed an icicle. The icicle, identified as a dense, hole-free structure, is strategically chosen to function as an intermediate shape for more intricate shape formation tasks. It is designed for easy exploration by a finite state agent, enabling the identification of tiles that can be lifted without breaking connectivity. Compared to the line shape, the icicle presents distinct advantages, including a reduced diameter and the presence of multiple removable tiles. We propose an algorithm that transforms an arbitrary initially connected tile structure into an icicle in 𝒪(n³) steps, matching the runtime of the line formation algorithm from prior work. Our theoretical contribution is accompanied by an extensive experimental analysis, indicating that our algorithm decreases the diameter of tile structures on average.","lang":"eng"}],"status":"public","_id":"54807","series_title":"Leibniz International Proceedings in Informatics (LIPIcs)","user_id":"55557","department":[{"_id":"79"}],"keyword":["Programmable Matter","Shape Formation","3D Model","Finite Automaton"],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-315-7"]},"place":"Dagstuhl, Germany","year":"2024","citation":{"apa":"Hinnenthal, K., Liedtke, D. J., &#38; Scheideler, C. (2024). Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures. In A. Casteigts &#38; F. Kuhn (Eds.), <i>3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)</i> (Vol. 292, p. 15:1–15:20). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SAND.2024.15\">https://doi.org/10.4230/LIPIcs.SAND.2024.15</a>","bibtex":"@inproceedings{Hinnenthal_Liedtke_Scheideler_2024, place={Dagstuhl, Germany}, series={Leibniz International Proceedings in Informatics (LIPIcs)}, title={Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures}, volume={292}, DOI={<a href=\"https://doi.org/10.4230/LIPIcs.SAND.2024.15\">10.4230/LIPIcs.SAND.2024.15</a>}, booktitle={3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)}, publisher={Schloss Dagstuhl – Leibniz-Zentrum für Informatik}, author={Hinnenthal, Kristian and Liedtke, David Jan and Scheideler, Christian}, editor={Casteigts, Arnaud and Kuhn, Fabian}, year={2024}, pages={15:1–15:20}, collection={Leibniz International Proceedings in Informatics (LIPIcs)} }","short":"K. Hinnenthal, D.J. Liedtke, C. Scheideler, in: A. Casteigts, F. Kuhn (Eds.), 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024), Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2024, p. 15:1–15:20.","mla":"Hinnenthal, Kristian, et al. “Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures.” <i>3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)</i>, edited by Arnaud Casteigts and Fabian Kuhn, vol. 292, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024, p. 15:1–15:20, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SAND.2024.15\">10.4230/LIPIcs.SAND.2024.15</a>.","ama":"Hinnenthal K, Liedtke DJ, Scheideler C. Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures. In: Casteigts A, Kuhn F, eds. <i>3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)</i>. Vol 292. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik; 2024:15:1–15:20. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SAND.2024.15\">10.4230/LIPIcs.SAND.2024.15</a>","chicago":"Hinnenthal, Kristian, David Jan Liedtke, and Christian Scheideler. “Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures.” In <i>3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)</i>, edited by Arnaud Casteigts and Fabian Kuhn, 292:15:1–15:20. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. <a href=\"https://doi.org/10.4230/LIPIcs.SAND.2024.15\">https://doi.org/10.4230/LIPIcs.SAND.2024.15</a>.","ieee":"K. Hinnenthal, D. J. Liedtke, and C. Scheideler, “Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures,” in <i>3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024)</i>, 2024, vol. 292, p. 15:1–15:20, doi: <a href=\"https://doi.org/10.4230/LIPIcs.SAND.2024.15\">10.4230/LIPIcs.SAND.2024.15</a>."},"page":"15:1–15:20","intvolume":"       292","date_updated":"2024-07-18T09:32:49Z","publisher":"Schloss Dagstuhl – Leibniz-Zentrum für Informatik","date_created":"2024-06-18T07:45:34Z","author":[{"id":"32229","full_name":"Hinnenthal, Kristian","last_name":"Hinnenthal","first_name":"Kristian"},{"last_name":"Liedtke","id":"55557","full_name":"Liedtke, David Jan","first_name":"David Jan"},{"first_name":"Christian","full_name":"Scheideler, Christian","id":"20792","last_name":"Scheideler"}],"volume":292,"title":"Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures","doi":"10.4230/LIPIcs.SAND.2024.15"},{"_id":"54802","department":[{"_id":"79"}],"user_id":"55557","keyword":["Programmable Matter","Coating","Finite Automaton","3D"],"language":[{"iso":"eng"}],"publication":"Structural Information and Communication Complexity","type":"book_chapter","editor":[{"first_name":"Yuval","full_name":"Emek, Yuval","last_name":"Emek"}],"abstract":[{"text":"Motivated by the prospect of nano-robots that assist human physiological functions at the nanoscale, we investigate the coating problem in the three-dimensional model for hybrid programmable matter. In this model, a single agent with strictly limited viewing range and the computational capability of a deterministic finite automaton can act on passive tiles by picking up a tile, moving, and placing it at some spot. The goal of the coating problem is to fill each node of some surface graph of size n with a tile. We first solve the problem on a restricted class of graphs with a single tile type, and then use constantly many tile types to encode this graph in certain surface graphs capturing the surface of 3D objects. Our algorithm requires O(n^2) steps, which is worst-case optimal compared to an agent with global knowledge and no memory restrictions.","lang":"eng"}],"status":"public","publisher":"Springer Nature Switzerland","date_updated":"2024-07-18T09:32:58Z","author":[{"first_name":"Irina","full_name":"Kostitsyna, Irina","last_name":"Kostitsyna"},{"first_name":"David Jan","last_name":"Liedtke","full_name":"Liedtke, David Jan","id":"55557"},{"first_name":"Christian","full_name":"Scheideler, Christian","id":"20792","last_name":"Scheideler"}],"date_created":"2024-06-18T07:36:04Z","title":"Universal Coating by 3D Hybrid Programmable Matter","doi":"10.1007/978-3-031-60603-8_21","publication_identifier":{"isbn":["9783031606021","9783031606038"],"issn":["0302-9743","1611-3349"]},"publication_status":"published","year":"2024","place":"Cham","citation":{"chicago":"Kostitsyna, Irina, David Jan Liedtke, and Christian Scheideler. “Universal Coating by 3D Hybrid Programmable Matter.” In <i>Structural Information and Communication Complexity</i>, edited by Yuval Emek. Cham: Springer Nature Switzerland, 2024. <a href=\"https://doi.org/10.1007/978-3-031-60603-8_21\">https://doi.org/10.1007/978-3-031-60603-8_21</a>.","ieee":"I. Kostitsyna, D. J. Liedtke, and C. Scheideler, “Universal Coating by 3D Hybrid Programmable Matter,” in <i>Structural Information and Communication Complexity</i>, Y. Emek, Ed. Cham: Springer Nature Switzerland, 2024.","ama":"Kostitsyna I, Liedtke DJ, Scheideler C. Universal Coating by 3D Hybrid Programmable Matter. In: Emek Y, ed. <i>Structural Information and Communication Complexity</i>. Springer Nature Switzerland; 2024. doi:<a href=\"https://doi.org/10.1007/978-3-031-60603-8_21\">10.1007/978-3-031-60603-8_21</a>","bibtex":"@inbook{Kostitsyna_Liedtke_Scheideler_2024, place={Cham}, title={Universal Coating by 3D Hybrid Programmable Matter}, DOI={<a href=\"https://doi.org/10.1007/978-3-031-60603-8_21\">10.1007/978-3-031-60603-8_21</a>}, booktitle={Structural Information and Communication Complexity}, publisher={Springer Nature Switzerland}, author={Kostitsyna, Irina and Liedtke, David Jan and Scheideler, Christian}, editor={Emek, Yuval}, year={2024} }","short":"I. Kostitsyna, D.J. Liedtke, C. Scheideler, in: Y. Emek (Ed.), Structural Information and Communication Complexity, Springer Nature Switzerland, Cham, 2024.","mla":"Kostitsyna, Irina, et al. “Universal Coating by 3D Hybrid Programmable Matter.” <i>Structural Information and Communication Complexity</i>, edited by Yuval Emek, Springer Nature Switzerland, 2024, doi:<a href=\"https://doi.org/10.1007/978-3-031-60603-8_21\">10.1007/978-3-031-60603-8_21</a>.","apa":"Kostitsyna, I., Liedtke, D. J., &#38; Scheideler, C. (2024). Universal Coating by 3D Hybrid Programmable Matter. In Y. Emek (Ed.), <i>Structural Information and Communication Complexity</i>. Springer Nature Switzerland. <a href=\"https://doi.org/10.1007/978-3-031-60603-8_21\">https://doi.org/10.1007/978-3-031-60603-8_21</a>"}},{"status":"public","type":"conference","language":[{"iso":"eng"}],"department":[{"_id":"34"},{"_id":"7"},{"_id":"79"}],"user_id":"15578","_id":"64104","citation":{"ieee":"C. Scheideler, K. Hinnenthal , and D. J. Liedtke, “Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures. SAND 2024: 15:1-15:20,” 2024.","chicago":"Scheideler, Christian, Kristian  Hinnenthal , and David Jan Liedtke. “Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures. SAND 2024: 15:1-15:20.” CoRR abs/2401.17734 (2024), 2024.","ama":"Scheideler C, Hinnenthal  K, Liedtke DJ. Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures. SAND 2024: 15:1-15:20. In: ; 2024.","short":"C. Scheideler, K. Hinnenthal , D.J. Liedtke, in: CoRR abs/2401.17734 (2024), 2024.","mla":"Scheideler, Christian, et al. <i>Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures. SAND 2024: 15:1-15:20</i>. 2024.","bibtex":"@inproceedings{Scheideler_Hinnenthal _Liedtke_2024, place={CoRR abs/2401.17734 (2024)}, title={Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures. SAND 2024: 15:1-15:20}, author={Scheideler, Christian and Hinnenthal , Kristian  and Liedtke, David Jan}, year={2024} }","apa":"Scheideler, C., Hinnenthal , K., &#38; Liedtke, D. J. (2024). <i>Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures. SAND 2024: 15:1-15:20</i>."},"place":"CoRR abs/2401.17734 (2024)","year":"2024","title":"Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures. SAND 2024: 15:1-15:20","date_created":"2026-02-10T10:12:18Z","author":[{"first_name":"Christian","id":"20792","full_name":"Scheideler, Christian","last_name":"Scheideler"},{"full_name":"Hinnenthal , Kristian ","last_name":"Hinnenthal ","first_name":"Kristian "},{"first_name":"David Jan","last_name":"Liedtke","id":"55557","full_name":"Liedtke, David Jan"}],"date_updated":"2026-02-11T09:12:05Z"},{"place":"SIROCCO 2024: 384-401","year":"2024","citation":{"chicago":"Scheideler, Christian, Irina  Kostitsyna, and David Jan Liedtke. “Universal Coating by 3D Hybrid Programmable Matter.” SIROCCO 2024: 384-401, 2024.","ieee":"C. Scheideler, I. Kostitsyna, and D. J. Liedtke, “Universal Coating by 3D Hybrid Programmable Matter.,” 2024.","ama":"Scheideler C, Kostitsyna I, Liedtke DJ. Universal Coating by 3D Hybrid Programmable Matter. In: ; 2024.","mla":"Scheideler, Christian, et al. <i>Universal Coating by 3D Hybrid Programmable Matter.</i> 2024.","short":"C. Scheideler, I. Kostitsyna, D.J. Liedtke, in: SIROCCO 2024: 384-401, 2024.","bibtex":"@inproceedings{Scheideler_Kostitsyna_Liedtke_2024, place={SIROCCO 2024: 384-401}, title={Universal Coating by 3D Hybrid Programmable Matter.}, author={Scheideler, Christian and Kostitsyna, Irina  and Liedtke, David Jan}, year={2024} }","apa":"Scheideler, C., Kostitsyna, I., &#38; Liedtke, D. J. (2024). <i>Universal Coating by 3D Hybrid Programmable Matter.</i>"},"date_updated":"2026-02-11T09:12:11Z","date_created":"2026-02-10T10:21:39Z","author":[{"last_name":"Scheideler","id":"20792","full_name":"Scheideler, Christian","first_name":"Christian"},{"last_name":"Kostitsyna","full_name":"Kostitsyna, Irina ","first_name":"Irina "},{"full_name":"Liedtke, David Jan","id":"55557","last_name":"Liedtke","first_name":"David Jan"}],"title":"Universal Coating by 3D Hybrid Programmable Matter.","type":"conference","status":"public","_id":"64106","department":[{"_id":"34"},{"_id":"7"},{"_id":"79"}],"user_id":"15578","language":[{"iso":"eng"}]},{"author":[{"full_name":"Liedtke, David Jan","id":"55557","last_name":"Liedtke","first_name":"David Jan"}],"supervisor":[{"full_name":"Scheideler, Christian","id":"20792","last_name":"Scheideler","first_name":"Christian"}],"date_created":"2021-09-29T12:37:39Z","date_updated":"2022-01-06T06:56:53Z","title":"Exploration and Convex Hull Construction in the Three-Dimensional Hybrid Model","has_accepted_license":"1","citation":{"bibtex":"@book{Liedtke_2021, title={Exploration and Convex Hull Construction in the Three-Dimensional Hybrid Model}, author={Liedtke, David Jan}, year={2021} }","short":"D.J. Liedtke, Exploration and Convex Hull Construction in the Three-Dimensional Hybrid Model, 2021.","mla":"Liedtke, David Jan. <i>Exploration and Convex Hull Construction in the Three-Dimensional Hybrid Model</i>. 2021.","apa":"Liedtke, D. J. (2021). <i>Exploration and Convex Hull Construction in the Three-Dimensional Hybrid Model</i>.","ama":"Liedtke DJ. <i>Exploration and Convex Hull Construction in the Three-Dimensional Hybrid Model</i>.; 2021.","chicago":"Liedtke, David Jan. <i>Exploration and Convex Hull Construction in the Three-Dimensional Hybrid Model</i>, 2021.","ieee":"D. J. Liedtke, <i>Exploration and Convex Hull Construction in the Three-Dimensional Hybrid Model</i>. 2021."},"year":"2021","user_id":"55557","department":[{"_id":"79"}],"_id":"25126","file_date_updated":"2021-09-29T12:34:47Z","language":[{"iso":"eng"}],"ddc":["000"],"keyword":["Robot Exploration","Finite Automaton","Hybrid Model for Programmable Matter","Convex Hull"],"type":"mastersthesis","file":[{"relation":"main_file","content_type":"application/pdf","file_id":"25128","access_level":"local","file_name":"Master - Thesis.pdf","file_size":10114825,"creator":"liedtke","date_created":"2021-09-29T12:34:47Z","date_updated":"2021-09-29T12:34:47Z"}],"status":"public","abstract":[{"text":"Motivated by the prospect of computing agents that explore unknown environments and construct convex hulls on the nanoscale, we investigate the capabilities and limitations of a single deterministic finite automaton robot in the three-dimensional hybrid model for programmable matter. In this model, active robots move on a set of passive tiles, called configuration, with the geometric shape of rhombic dodecahedra on the adjacency graph of the face-centered cubic sphere-packing. We show that the exploration problem is equally hard in the hybrid model and in three-dimensional mazes, in which tiles have the shape of cubes and are positioned at the vertices of $\\mathbb{Z}^3$. Thereby, a single robot with a constant number of pebbles cannot solve this problem in the hybrid model on arbitrary configurations. We provide algorithms for a robot with two pebbles that solve the exploration problem in the subclass of compact configurations of size $n$ in $\\O(n^3)$ rounds. Further, we investigate the robot's capabilities of detection and hull construction in terms of restricted orientation convexity. We show that a robot without any pebble can detect strong $\\O$-convexity in $\\O(n)$ rounds, but cannot detect weak $\\O$-convexity, not even if provided with a single pebble. Assuming that a robot can construct tiles from scratch and deconstruct previously constructed tiles, we show that the strong $\\O$-hull of any given configuration of size $n$ can be constructed in $\\O(n^4)$ rounds, even if the robot cannot distinguish constructed from native tiles.","lang":"eng"}]},{"status":"public","file":[{"content_type":"application/pdf","relation":"main_file","date_created":"2021-09-29T12:21:24Z","creator":"liedtke","date_updated":"2021-09-29T12:21:24Z","file_name":"Bachelor - Thesis.pdf","access_level":"local","file_id":"25124","file_size":6746519}],"abstract":[{"lang":"eng","text":"We consider a group of $n$ autonomous mobile robots of which $m$ are stationary thus cannot move. Robots are represented by points in the Euclidean plane. They have no memory, do not communicate or share a common coordinate system and they move solely based on the positioning of other robots within their limited viewing range of 1. The goal is to gather the robots inside of the convex hull of all stationary robots. A variant of this problem, the general gathering problem, has been studied in various different time models. In this work, we consider a continuous time model, where robots continuously observe their neighbors, compute the next target of movement and move with a speed limit of 1 at any time. Regarding the robots' local strategy, we only study contracting algorithms in which every robot that is positioned on the border of the convex hull of all robots moves into this hull. We present a time bound of $\\mathcal{O}(nd)$ for any general contracting algorithms in a configuration with only a single stationary robot. For configurations with more stationary robots, we prove that robots converge against the convex hull of all stationary robots and that no upper bound on the runtime exists. For the specific contracting algorithms Go-To-The-Left, Go-On-Bisector and Go-To-The-Middle, we provide linear time bounds."}],"type":"bachelorsthesis","language":[{"iso":"eng"}],"file_date_updated":"2021-09-29T12:21:24Z","ddc":["000"],"department":[{"_id":"63"}],"user_id":"55557","_id":"25121","citation":{"apa":"Liedtke, D. J. (2018). <i>Influence of Stationary Robots on Continuous Robot Formation Problems</i>.","short":"D.J. Liedtke, Influence of Stationary Robots on Continuous Robot Formation Problems, 2018.","bibtex":"@book{Liedtke_2018, title={Influence of Stationary Robots on Continuous Robot Formation Problems}, author={Liedtke, David Jan}, year={2018} }","mla":"Liedtke, David Jan. <i>Influence of Stationary Robots on Continuous Robot Formation Problems</i>. 2018.","ieee":"D. J. Liedtke, <i>Influence of Stationary Robots on Continuous Robot Formation Problems</i>. 2018.","chicago":"Liedtke, David Jan. <i>Influence of Stationary Robots on Continuous Robot Formation Problems</i>, 2018.","ama":"Liedtke DJ. <i>Influence of Stationary Robots on Continuous Robot Formation Problems</i>.; 2018."},"year":"2018","has_accepted_license":"1","title":"Influence of Stationary Robots on Continuous Robot Formation Problems","author":[{"last_name":"Liedtke","id":"55557","full_name":"Liedtke, David Jan","first_name":"David Jan"}],"date_created":"2021-09-29T12:30:40Z","supervisor":[{"first_name":"Friedhelm","last_name":"Meyer auf der Heide","full_name":"Meyer auf der Heide, Friedhelm","id":"15523"}],"date_updated":"2022-01-06T06:56:52Z"}]