{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:33:09Z","timestamp":1771036389867,"version":"3.50.1"},"reference-count":71,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2022,6,24]],"date-time":"2022-06-24T00:00:00Z","timestamp":1656028800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,6,24]],"date-time":"2022-06-24T00:00:00Z","timestamp":1656028800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"TBD"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We provide algorithmic methods for connected reconfiguration of lattice-based cellular structures by finite-state robots, motivated by large-scale constructions in space. We present algorithms that are able to detect and reconfigure arbitrary polyominoes, while also preserving connectivity of a structure during reconfiguration; we also provide mathematical proofs and performance guarantees. Specific results include methods for determining a bounding box, scaling a given arrangement, and adapting more general algorithms for transforming polyominoes.<\/jats:p>","DOI":"10.1007\/s00453-022-00995-z","type":"journal-article","created":{"date-parts":[[2022,6,24]],"date-time":"2022-06-24T21:04:46Z","timestamp":1656104686000},"page":"2954-2986","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Connected Reconfiguration of Lattice-Based Cellular Structures by Finite-Memory Robots"],"prefix":"10.1007","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9062-4241","authenticated-orcid":false,"given":"S\u00e1ndor P.","family":"Fekete","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eike","family":"Niehs","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Scheffer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arne","family":"Schmidt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,6,24]]},"reference":[{"key":"995_CR1","unstructured":"Abdel-Rahman, A., Becker, A.T., Biediger, D.E., Cheung, K.C., Fekete, S.P., Gershenfeld, N.A., Hugo, S., Jenett, B., Keldenich, P., Niehs, E., Rieck, C., Schmidt, A., Scheffer, C., Yannuzzi, M.: Space ants: Constructing and reconfiguring large-scale structures with finite automata. In: Symposium on Computational Geometry (SoCG), pages 73:1\u201373:7, (2020). Video available at https:\/\/www.ibr.cs.tu-bs.de\/users\/fekete\/Videos\/SoCG\/2020\/Space_final.mp4"},{"issue":"3","key":"995_CR2","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1137\/S0363012993249195","volume":"33","author":"S Alpern","year":"1995","unstructured":"Alpern, S.: The rendezvous search problem. SIAM J. Control. Optim. 33(3), 673\u2013683 (1995)","journal-title":"SIAM J. Control. Optim."},{"issue":"2","key":"995_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1921659.1921663","volume":"7","author":"C Amb\u00fchl","year":"2011","unstructured":"Amb\u00fchl, C., Gasieniec, L., Pelc, A., Radzik, T., Zhang, X.: Tree exploration with logarithmic memory. ACM Trans. Algorithms (TALG) 7(2), 1\u201321 (2011)","journal-title":"ACM Trans. Algorithms (TALG)"},{"issue":"4","key":"995_CR4","doi-asserted-by":"publisher","first-page":"839","DOI":"10.2307\/3214827","volume":"27","author":"EJ Anderson","year":"1990","unstructured":"Anderson, E.J., Weber, R.R.: The rendezvous problem on discrete locations. J. Appl. Probab. 27(4), 839\u2013851 (1990)","journal-title":"J. Appl. Probab."},{"key":"995_CR5","doi-asserted-by":"crossref","unstructured":"Balanza-Martinez, J., Luchsinger, A., Caballero, D., Reyes, R., Cantu, A.A., Schweller, R., Garcia, L.A., Wylie, T.: Full tilt: universal constructors for general shapes with uniform external forces. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2689\u20132708 (2019)","DOI":"10.1137\/1.9781611975482.167"},{"key":"995_CR6","doi-asserted-by":"crossref","unstructured":"Becker, A.T., Fekete, S.P., Keldenich, P., Krupke, D., Rieck, C., Scheffer, C., Schmidt, A.: Tilt assembly: algorithms for micro-factories that build objects with uniform external forces. Algorithmica, 82(2), 1\u201323 (2017)","DOI":"10.1007\/s00453-018-0483-9"},{"key":"995_CR7","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Slonim, D.K.: The power of team exploration: two robots can learn unlabeled directed graphs. In: Symposium on Foundations of Computer Science (FOCS), pages 75\u201385 (1994)","DOI":"10.1109\/SFCS.1994.365703"},{"key":"995_CR8","doi-asserted-by":"crossref","unstructured":"Blum, M., Kozen, D.: On the power of the compass (or, why mazes are easier to search than graphs). In: Symposium on Foundations of Computer Science (FOCS), pages 132\u2013142 (1978)","DOI":"10.1109\/SFCS.1978.30"},{"issue":"4","key":"995_CR9","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1109\/TRO.2011.2121170","volume":"27","author":"P Brass","year":"2011","unstructured":"Brass, P., Cabrera-Mora, F., Gasparri, A., Xiao, J.: Multirobot tree and graph exploration. IEEE Trans. Rob. 27(4), 707\u2013717 (2011)","journal-title":"IEEE Trans. Rob."},{"issue":"4","key":"995_CR10","doi-asserted-by":"publisher","first-page":"1383","DOI":"10.1007\/s00453-017-0318-0","volume":"80","author":"C Chalk","year":"2018","unstructured":"Chalk, C., Martinez, E., Schweller, R., Vega, L., Winslow, A., Wylie, T.: Optimal staged self-assembly of general shapes. Algorithmica 80(4), 1383\u20131409 (2018)","journal-title":"Algorithmica"},{"issue":"6151","key":"995_CR11","doi-asserted-by":"publisher","first-page":"1219","DOI":"10.1126\/science.1240889","volume":"341","author":"KC Cheung","year":"2013","unstructured":"Cheung, K.C., Gershenfeld, N.: Reversibly assembled cellular composite materials. Sci. 341(6151), 1219\u20131221 (2013)","journal-title":"Sci."},{"issue":"4","key":"995_CR12","doi-asserted-by":"publisher","first-page":"829","DOI":"10.1137\/100796534","volume":"41","author":"M Cieliebak","year":"2012","unstructured":"Cieliebak, M., Flocchini, P., Prencipe, G., Santoro, N.: Distributed computing by mobile robots: Gathering. SIAM J. Comput. 41(4), 829\u2013879 (2012)","journal-title":"SIAM J. Comput."},{"key":"995_CR13","doi-asserted-by":"crossref","unstructured":"Costa, A., Abdel-Rahman, A., Jenett, B., Gershenfeld, N., Kostitsyna, I., Cheung, K.: Algorithmic approaches to reconfigurable assembly systems. In: IEEE Aerospace Conference, pages 1\u20138 (2019)","DOI":"10.1109\/AERO.2019.8741572"},{"issue":"5","key":"995_CR14","doi-asserted-by":"publisher","DOI":"10.1088\/1361-665X\/ab0ea2","volume":"28","author":"NB Cramer","year":"2019","unstructured":"Cramer, N.B., Cellucci, D.W., Formoso, O.B., Gregg, C.E., Jenett, B.E., Kim, J.H., Lendraitis, M., Swei, S.S., Trinh, G.T., Trinh, K.V., et al.: Elastic shape morphing of ultralight structures by programmable assembly. Smart Mater. Struct. 28(5), 055006 (2019)","journal-title":"Smart Mater. Struct."},{"issue":"6","key":"995_CR15","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1016\/j.tcs.2008.10.005","volume":"410","author":"J Czyzowicz","year":"2009","unstructured":"Czyzowicz, J., Gasieniec, L., Pelc, A.: Gathering few fat mobile robots in the plane. Theoret. Comput. Sci. 410(6), 481\u2013499 (2009)","journal-title":"Theoret. Comput. Sci."},{"key":"995_CR16","unstructured":"D\u2019Angelo, G., D\u2019Emidio, M., Das, S., Navarra, A., Prencipe, G.: Leader election and compaction for asynchronous silent programmable matter. In: Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, pages 276\u2013284 (2020)"},{"key":"995_CR17","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1007\/978-1-4614-6825-7_13","volume-title":"Search Theory","author":"G D\u2019Angelo","year":"2013","unstructured":"D\u2019Angelo, G., Stefano, G.D., Navarra, A.: Gathering asynchronous and oblivious robots on basic graph topologies under the look-compute-move model. In: Alpern, S., Fokkink, R., Gasieniec, L., Lindelauf, R., Subrahmanian, V. (eds.) Search Theory, pp. 197\u2013222. Springer, New York (2013)"},{"issue":"1","key":"995_CR18","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/j.tcs.2007.05.011","volume":"385","author":"S Das","year":"2007","unstructured":"Das, S., Flocchini, P., Kutten, S., Nayak, A., Santoro, N.: Map construction of unknown graphs by multiple agents. Theoret. Comput. Sci. 385(1), 34\u201348 (2007)","journal-title":"Theoret. Comput. Sci."},{"key":"995_CR19","doi-asserted-by":"crossref","unstructured":"Daymude, J.J., Gmyr, R., Richa, A.W., Scheideler, C., Strothmann, T.: Improved leader election for self-organizing programmable matter. In: Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS), pages 127\u2013140 (2017)","DOI":"10.1007\/978-3-319-72751-6_10"},{"issue":"3","key":"995_CR20","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/s11047-008-9073-0","volume":"7","author":"ED Demaine","year":"2008","unstructured":"Demaine, E.D., Demaine, M.L., Fekete, S.P., Ishaque, M., Rafalin, E., Schweller, R.T., Souvaine, D.L.: Staged self-assembly: nanomanufacture of arbitrary shapes with o (1) glues. Nat. Comput. 7(3), 347\u2013370 (2008)","journal-title":"Nat. Comput."},{"key":"995_CR21","doi-asserted-by":"crossref","unstructured":"Derakhshandeh, Z., Dolev, S., Gmyr, R., Richa, A.W., Scheideler, C., Strothmann, T.: Brief announcement: Amoebot - a new model for programmable matter. In: ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 220\u2013222 (2014)","DOI":"10.1145\/2612669.2612712"},{"key":"995_CR22","doi-asserted-by":"crossref","unstructured":"Derakhshandeh, Z., Gmyr, R., Porter, A., Richa, A.W., Scheideler, C., Strothmann, T.: On the runtime of universal coating for programmable matter. In: International Conference on DNA Computing and Molecular Programming (DNA), pages 148\u2013164 (2016)","DOI":"10.1007\/978-3-319-43994-5_10"},{"key":"995_CR23","doi-asserted-by":"crossref","unstructured":"Derakhshandeh, Z., Gmyr, R., Richa, A.W., Scheideler, C., Strothmann, T.: An algorithmic framework for shape formation problems in self-organizing particle systems. In: International Conference on Nanoscale Computing and Communication (NANOCOM), pages 21:1\u201321:2 (2015)","DOI":"10.1145\/2800795.2800829"},{"key":"995_CR24","doi-asserted-by":"crossref","unstructured":"Derakhshandeh, Z., Gmyr, R., Richa, A.W., Scheideler, C., Strothmann, T.: Universal shape formation for programmable matter. In: ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 289\u2013299 (2016)","DOI":"10.1145\/2935764.2935784"},{"key":"995_CR25","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/j.tcs.2016.02.039","volume":"671","author":"Z Derakhshandeh","year":"2017","unstructured":"Derakhshandeh, Z., Gmyr, R., Richa, A.W., Scheideler, C., Strothmann, T.: Universal coating for programmable matter. Theoret. Comput. Sci. 671, 56\u201368 (2017)","journal-title":"Theoret. Comput. Sci."},{"key":"995_CR26","doi-asserted-by":"crossref","unstructured":"Derakhshandeh, Z., Gmyr, R., Strothmann, T., Bazzi, R., Richa, A.W., Scheideler, C.: Leader election and shape formation with self-organizing programmable matter. In: 21st International Conference on DNA Computing and Molecular Programming (DNA), pages 117\u2013132 (2015)","DOI":"10.1007\/978-3-319-21999-8_8"},{"issue":"1","key":"995_CR27","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/s00453-006-0074-2","volume":"46","author":"A Dessmark","year":"2006","unstructured":"Dessmark, A., Fraigniaud, P., Kowalski, D.R., Pelc, A.: Deterministic rendezvous in graphs. Algorithmica 46(1), 69\u201396 (2006)","journal-title":"Algorithmica"},{"issue":"9","key":"995_CR28","doi-asserted-by":"publisher","first-page":"1241","DOI":"10.1007\/s00607-018-0595-8","volume":"101","author":"S Devismes","year":"2019","unstructured":"Devismes, S., Lamani, A., Petit, F., Tixeuil, S.: Optimal torus exploration by oblivious robots. Comput. 101(9), 1241\u20131264 (2019)","journal-title":"Comput."},{"issue":"1","key":"995_CR29","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/s00446-019-00350-6","volume":"33","author":"GA Di Luna","year":"2020","unstructured":"Di Luna, G.A., Flocchini, P., Santoro, N., Viglietta, G., Yamauchi, Y.: Shape formation by programmable particles. Distrib. Comput. 33(1), 69\u2013101 (2020)","journal-title":"Distrib. Comput."},{"issue":"2","key":"995_CR30","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/s00446-016-0278-7","volume":"30","author":"G Di Stefano","year":"2017","unstructured":"Di Stefano, G., Navarra, A.: Optimal gathering of oblivious robots in anonymous graphs and its application on trees and rings. Distrib. Comput. 30(2), 75\u201386 (2017)","journal-title":"Distrib. Comput."},{"issue":"1","key":"995_CR31","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1016\/j.jalgor.2003.10.002","volume":"51","author":"K Diks","year":"2004","unstructured":"Diks, K., Fraigniaud, P., Kranakis, E., Pelc, A.: Tree exploration with little memory. J. Algorithms 51(1), 38\u201363 (2004)","journal-title":"J. Algorithms"},{"key":"995_CR32","doi-asserted-by":"crossref","unstructured":"Fekete, S.P., Gmyr, R., Hugo, S., Keldenich, P., Scheffer, C., Schmidt, A.: Cadbots: algorithmic aspects of manipulating programmable matter with finite automata. Algorithmica, 83(1), 1\u201326 (2020)","DOI":"10.1007\/s00453-020-00761-z"},{"key":"995_CR33","doi-asserted-by":"crossref","unstructured":"Fekete, S.P., Niehs, E., Scheffer, C., Schmidt, A.: Connected reconfiguration of lattice-based cellular structures by finite-memory robots. In: International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, pages 60\u201375. Springer (2020)","DOI":"10.1007\/978-3-030-62401-9_5"},{"issue":"6197","key":"995_CR34","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1126\/science.1252610","volume":"345","author":"S Felton","year":"2014","unstructured":"Felton, S., Tolley, M., Demaine, E., Rus, D., Wood, R.: A method for building self-folding machines. Sci. 345(6197), 644\u2013646 (2014)","journal-title":"Sci."},{"key":"995_CR35","doi-asserted-by":"crossref","unstructured":"Fleischer, R., Trippen, G.: Exploring an unknown graph efficiently. In: European Symposium on Algorithms (ESA), pages 11\u201322 (2005)","DOI":"10.1007\/11561071_4"},{"key":"995_CR36","doi-asserted-by":"crossref","unstructured":"Flocchini, P., Prencipe, G., Santoro, N.: Distributed computing by mobile entities. Current Research in Moving and Computing, vol. 11340. Springer LNCS (2019)","DOI":"10.1007\/978-3-030-11072-7"},{"issue":"1","key":"995_CR37","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/j.tcs.2005.01.001","volume":"337","author":"P Flocchini","year":"2005","unstructured":"Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Gathering of asynchronous robots with limited visibility. Theoret. Comput. Sci. 337(1), 147\u2013168 (2005)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"995_CR38","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1002\/net.20127","volume":"48","author":"P Fraigniaud","year":"2006","unstructured":"Fraigniaud, P., Gasieniec, L., Kowalski, D.R., Pelc, A.: Collective tree exploration. Networks 48(3), 166\u2013177 (2006)","journal-title":"Networks"},{"key":"995_CR39","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Ilcinkas, D.: Digraphs exploration with little memory. In: Symposium on Theoretical Aspects of Computer Science (STACS), pages 246\u2013257 (2004)","DOI":"10.1007\/978-3-540-24749-4_22"},{"issue":"2\u20133","key":"995_CR40","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1016\/j.tcs.2005.07.014","volume":"345","author":"P Fraigniaud","year":"2005","unstructured":"Fraigniaud, P., Ilcinkas, D., Peer, G., Pelc, A., Peleg, D.: Graph Exploration by a Finite Automaton. Theoret. Comput. Sci. 345(2\u20133), 331\u2013344 (2005)","journal-title":"Theoret. Comput. Sci."},{"key":"995_CR41","doi-asserted-by":"crossref","unstructured":"Gasieniec, L., Radzik, T.: Memory efficient anonymous graph exploration. In: Workshop on Graph-Theoretic Concepts in Computer Science (WG), pages 14\u201329 (2008)","DOI":"10.1007\/978-3-540-92248-3_2"},{"key":"995_CR42","doi-asserted-by":"crossref","unstructured":"Gilpin, K., Knaian, A., Rus, D.: Robot pebbles: One centimeter modules for programmable matter through self-disassembly. In: IEEE International Conference on Robotics and Automation (ICRA), pages 2485\u20132492 (May 2010)","DOI":"10.1109\/ROBOT.2010.5509817"},{"key":"995_CR43","unstructured":"Gmyr, R., Hinnenthal, K., Kostitsyna, I., Kuhn, F., Rudolph, D., Scheideler, C.: Shape Recognition by a Finite Automaton Robot. In: International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 52:1\u201352:15 (2018)"},{"key":"995_CR44","doi-asserted-by":"crossref","unstructured":"Gmyr, R., Hinnenthal, K., Kostitsyna, I., Kuhn, F., Rudolph, D., Scheideler, C., Strothmann, T.: Forming tile shapes with simple robots. In: International Conference on DNA Computing and Molecular Programming (DNA), pages 122\u2013138 (2018)","DOI":"10.1007\/978-3-030-00030-1_8"},{"key":"995_CR45","unstructured":"Gmyr, R., Kostitsyna, I., Kuhn, F., Scheideler, C., Strothmann, T.: Forming tile shapes with a single robot. In: European Workshop on Computational Geometry (EuroCG), pages 9\u201312 (2017)"},{"key":"995_CR46","unstructured":"Goldstein, S.C., Mowry, T.: Claytronics: A scalable basis for future robots. Robosphere, 1\u20136 (2004)"},{"key":"995_CR47","doi-asserted-by":"crossref","unstructured":"Gregg, C.E., Jenett, B., Cheung, K.C.: Assembled, modular hardware architectures - what price reconfigurability? In: IEEE Aerospace Conference, pages 1\u201310 (2019)","DOI":"10.1109\/AERO.2019.8741533"},{"issue":"9","key":"995_CR48","doi-asserted-by":"publisher","first-page":"1800213","DOI":"10.1002\/adem.201800213","volume":"20","author":"CE Gregg","year":"2018","unstructured":"Gregg, C.E., Kim, J.H., Cheung, K.C.: Ultra-light and scalable composite lattice materials. Adv. Eng. Mater. 20(9), 1800213 (2018)","journal-title":"Adv. Eng. Mater."},{"issue":"28","key":"995_CR49","doi-asserted-by":"publisher","first-page":"12441","DOI":"10.1073\/pnas.0914069107","volume":"107","author":"E Hawkes","year":"2010","unstructured":"Hawkes, E., An, B., Benbernou, N.M., Tanaka, H., Kim, S., Demaine, E.D., Rus, D., Wood, R.J.: Programmable matter by folding. Proc. Natl. Acad. Sci. 107(28), 12441\u201312445 (2010)","journal-title":"Proc. Natl. Acad. Sci."},{"issue":"4","key":"995_CR50","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1007\/s10514-015-9421-8","volume":"38","author":"F Hurtado","year":"2015","unstructured":"Hurtado, F., Molina, E., Ramaswami, S., Sacrist\u00e1n, V.: Distributed reconfiguration of 2D lattice-based modular robotic systems. Auton. Robot. 38(4), 383\u2013413 (2015)","journal-title":"Auton. Robot."},{"issue":"1\u20133","key":"995_CR51","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1016\/j.tcs.2008.03.035","volume":"401","author":"D Ilcinkas","year":"2008","unstructured":"Ilcinkas, D.: Setting port numbers for fast graph exploration. Theoret. Comput. Sci. 401(1\u20133), 236\u2013242 (2008)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"995_CR52","doi-asserted-by":"publisher","first-page":"4019","DOI":"10.1109\/LRA.2019.2930486","volume":"4","author":"B Jenett","year":"2019","unstructured":"Jenett, B., Abdel-Rahman, A., Cheung, K.C., Gershenfeld, N.: Material-robot system for assembly of discrete cellular structures. IEEE Robot. Autom. Lett. 4(4), 4019\u20134026 (2019)","journal-title":"IEEE Robot. Autom. Lett."},{"issue":"1","key":"995_CR53","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1089\/soro.2016.0032","volume":"4","author":"B Jenett","year":"2017","unstructured":"Jenett, B., Calisch, S., Cellucci, D., Cramer, N., Gershenfeld, N., Swei, S., Cheung, K.C.: Digital morphing wing: active wing shaping concept using composite lattice-based cellular structures. Soft Rob. 4(1), 33\u201348 (2017)","journal-title":"Soft Rob."},{"key":"995_CR54","doi-asserted-by":"crossref","unstructured":"Jenett, B., Cellucci, D.: A mobile robot for locomotion through a 3d periodic lattice environment. In: IEEE International Conference on Robotics and Automation (ICRA), pages 5474\u20135479 (2017)","DOI":"10.1109\/ICRA.2017.7989644"},{"key":"995_CR55","doi-asserted-by":"crossref","unstructured":"Jenett, B., Cellucci, D., Gregg, C., Cheung, K.: Meso-scale digital materials: modular, reconfigurable, lattice-based structures. In: ASME International Manufacturing Science and Engineering Conference (MSEC) (2016)","DOI":"10.1115\/MSEC2016-8767"},{"key":"995_CR56","doi-asserted-by":"crossref","unstructured":"Jenett, B., Cheung, K.: Bill-e: Robotic platform for locomotion and manipulation of lightweight space structures. In: AIAA\/AHS Adaptive Structures Conference, page 1876 (2017)","DOI":"10.2514\/6.2017-1876"},{"key":"995_CR57","doi-asserted-by":"crossref","unstructured":"Jenett, B., Gregg, C., Cellucci, D., Cheung, K.: Design of multifunctional hierarchical space structures. In: IEEE Aerospace Conference, pages 1\u201310 (2017)","DOI":"10.1109\/AERO.2017.7943913"},{"key":"995_CR58","doi-asserted-by":"crossref","unstructured":"Kamei, S., Lamani, A., Ooshita, F., Tixeuil, S.: Asynchronous mobile robot gathering from symmetric configurations without global multiplicity detection. In Kosowski, A., Yamashita, M. (Eds.), International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 150\u2013161. Springer LNCS","DOI":"10.1007\/978-3-642-22212-2_14"},{"key":"995_CR59","unstructured":"Kim, Y., Katayama, Y., Wada, K.: Pairbot: A novel model for autonomous mobile robot systems consisting of paired robots. arXiv preprintarXiv:2009.14426, (2020)"},{"key":"995_CR60","doi-asserted-by":"crossref","unstructured":"Knaian, A.N., Cheung, K.C., Lobovsky, M.B., Oines, A.J., Schmidt-Neilsen, P., Gershenfeld, N.A.: The milli-motein: A self-folding chain of programmable matter with a one centimeter module pitch. In: IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 1447\u20131453 (2012)","DOI":"10.1109\/IROS.2012.6385904"},{"issue":"3","key":"995_CR61","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/j.tcs.2005.12.016","volume":"355","author":"GD Marco","year":"2006","unstructured":"Marco, G.D., Gargano, L., Kranakis, E., Krizanc, D., Pelc, A., Vaccaro, U.: Asynchronous deterministic rendezvous in graphs. Theoret. Comput. Sci. 355(3), 315\u2013326 (2006)","journal-title":"Theoret. Comput. Sci."},{"key":"995_CR62","doi-asserted-by":"crossref","unstructured":"Naz, A., Piranda, B., Bourgeois, J., Goldstein, S.C.: A distributed self-reconfiguration algorithm for cylindrical lattice-based modular robots. In: IEEE International Symposium on Network Computing and Applications (NCA), pages 254\u2013263 (2016)","DOI":"10.1109\/NCA.2016.7778628"},{"key":"995_CR63","doi-asserted-by":"crossref","unstructured":"Niehs, E., Schmidt, A., Scheffer, C., Biediger, D.E., Yannuzzi, M., Jenett, B., Abdel-Rahman, A., Cheung, K.C., Becker, A.T., Fekete, S.P.: Recognition and reconfiguration of lattice-based cellular structures by simple robots. In: 2020 IEEE International Conference on Robotics and Automation (ICRA), pages 8252\u20138259. IEEE (2020)","DOI":"10.1109\/ICRA40945.2020.9196700"},{"issue":"2","key":"995_CR64","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1006\/jagm.1999.1043","volume":"33","author":"P Panaite","year":"1999","unstructured":"Panaite, P., Pelc, A.: Exploring unknown undirected graphs. J. Algorithms 33(2), 281\u2013295 (1999)","journal-title":"J. Algorithms"},{"issue":"2","key":"995_CR65","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/s11047-013-9379-4","volume":"13","author":"MJ Patitz","year":"2014","unstructured":"Patitz, M.J.: An introduction to tile-based self-assembly and a survey of recent results. Nat. Comput. 13(2), 195\u2013224 (2014)","journal-title":"Nat. Comput."},{"issue":"4","key":"995_CR66","doi-asserted-by":"publisher","first-page":"3521","DOI":"10.1109\/LRA.2018.2853758","volume":"3","author":"A Schmidt","year":"2018","unstructured":"Schmidt, A., Manzoor, S., Huang, L., Becker, A.T., Fekete, S.P.: Efficient parallel self-assembly under uniform control inputs. IEEE Robot. Autom. Lett. 3(4), 3521\u20133528 (2018)","journal-title":"IEEE Robot. Autom. Lett."},{"issue":"3","key":"995_CR67","doi-asserted-by":"publisher","first-page":"12:1","DOI":"10.1145\/2601068","volume":"10","author":"A Ta-Shma","year":"2014","unstructured":"Ta-Shma, A., Zwick, U.: Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences. ACM Trans. Algorithms 10(3), 12:1-12:15 (2014)","journal-title":"ACM Trans. Algorithms"},{"key":"995_CR68","unstructured":"Tucci, T., Piranda, B., Bourgeois, J.: A distributed self-assembly planning algorithm for modular robots. In: International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 550\u2013558 (2018)"},{"key":"995_CR69","unstructured":"Winfree, E.: Algorithmic self-assembly of DNA. PhD thesis, California Institute of Technology (1998)"},{"issue":"6693","key":"995_CR70","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1038\/28998","volume":"394","author":"E Winfree","year":"1998","unstructured":"Winfree, E., Liu, F., Wenzler, L.A., Seeman, N.C.: Design and self-assembly of two-dimensional DNA crystals. Nature 394(6693), 539 (1998)","journal-title":"Nature"},{"key":"995_CR71","doi-asserted-by":"crossref","unstructured":"Woods, D., Chen, H.-L., Goodfriend, S., Dabby, N., Winfree, E., Yin, P.: Active self-assembly of algorithmic shapes and patterns in polylogarithmic time. In: 4th Conference on Innovations in Theoretical Computer Science (IITCS), pages 353\u2013354 (2013)","DOI":"10.1145\/2422436.2422476"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00995-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00995-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00995-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,27]],"date-time":"2024-09-27T19:29:07Z","timestamp":1727465347000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00995-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,24]]},"references-count":71,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["995"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00995-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,6,24]]},"assertion":[{"value":"30 July 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 June 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 June 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 September 2022","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Missing Open Access funding information has been added in the Funding Note.","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}