{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T12:56:39Z","timestamp":1742993799578,"version":"3.40.3"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030624002"},{"type":"electronic","value":"9783030624019"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-62401-9_5","type":"book-chapter","created":{"date-parts":[[2020,10,27]],"date-time":"2020-10-27T08:04:15Z","timestamp":1603785855000},"page":"60-75","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Connected Reconfiguration of Lattice-Based Cellular Structures by Finite-Memory Robots"],"prefix":"10.1007","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"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1785-9105","authenticated-orcid":false,"given":"Eike","family":"Niehs","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3471-2706","authenticated-orcid":false,"given":"Christian","family":"Scheffer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8950-3963","authenticated-orcid":false,"given":"Arne","family":"Schmidt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,10,28]]},"reference":[{"key":"5_CR1","unstructured":"Abdel-Rahman, A., et al.: Space ants: constructing and reconfiguring large-scale structures with finite automata. In: Symposium on Computational Geometry (SoCG), pp. 73:1\u201373:7 (2020). https:\/\/www.ibr.cs.tu-bs.de\/users\/fekete\/Videos\/SoCG\/2020\/Space_final.mp4"},{"key":"5_CR2","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), pp. 75\u201385 (1994)"},{"key":"5_CR3","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), pp. 132\u2013142 (1978)","DOI":"10.1109\/SFCS.1978.30"},{"issue":"4","key":"5_CR4","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. Robot. 27(4), 707\u2013717 (2011)","journal-title":"IEEE Trans. Robot."},{"key":"5_CR5","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/j.tcs.2012.01.035","volume":"444","author":"J Czyzowicz","year":"2012","unstructured":"Czyzowicz, J., Dobrev, S., Gasieniec, L., Ilcinkas, D., Jansson, J., Klasing, R., Lignos, I., Martin, R., Sadakane, K., Sung, W.-K.: More efficient periodic traversal in anonymous undirected graphs. Theor. Comput. Sci. 444, 60\u201376 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"5_CR6","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, pp. 276\u2013284 (2020)"},{"issue":"1","key":"5_CR7","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. Theor. Comput. Sci. 385(1), 34\u201348 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"5_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/978-3-319-72751-6_10","volume-title":"Algorithms for Sensor Systems","author":"JJ Daymude","year":"2017","unstructured":"Daymude, J.J., Gmyr, R., Richa, A.W., Scheideler, C., Strothmann, T.: Improved leader election for self-organizing programmable matter. In: Fern\u00e1ndez Anta, A., Jurdzinski, T., Mosteiro, M.A., Zhang, Y. (eds.) ALGOSENSORS 2017. LNCS, vol. 10718, pp. 127\u2013140. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-72751-6_10"},{"key":"5_CR9","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), pp. 220\u2013222 (2014)","DOI":"10.1145\/2612669.2612712"},{"key":"5_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/978-3-319-43994-5_10","volume-title":"DNA Computing and Molecular Programming","author":"Z Derakhshandeh","year":"2016","unstructured":"Derakhshandeh, Z., Gmyr, R., Porter, A., Richa, A.W., Scheideler, C., Strothmann, T.: On the runtime of universal coating for programmable matter. In: Rondelez, Y., Woods, D. (eds.) DNA 2016. LNCS, vol. 9818, pp. 148\u2013164. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-43994-5_10"},{"key":"5_CR11","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), pp. 21:1\u201321:2 (2015)","DOI":"10.1145\/2800795.2800829"},{"key":"5_CR12","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. Theor. Comput. Sci. 671, 56\u201368 (2017)","journal-title":"Theor. Comput. Sci."},{"key":"5_CR13","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: International Conference on DNA Computing and Molecular Programming (DNA), pp. 117\u2013132 (2015)","DOI":"10.1007\/978-3-319-21999-8_8"},{"issue":"1","key":"5_CR14","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/s00446-019-00350-6","volume":"33","author":"GA Di Luna","year":"2019","unstructured":"Di Luna, G.A., Flocchini, P., Santoro, N., Viglietta, G., Yamauchi, Y.: Shape formation by programmable particles. Distrib. Comput. 33(1), 69\u2013101 (2019). https:\/\/doi.org\/10.1007\/s00446-019-00350-6","journal-title":"Distrib. Comput."},{"issue":"1","key":"5_CR15","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":"5_CR16","series-title":"Springer Proceedings in Advanced Robotics","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1007\/978-3-030-44051-0_42","volume-title":"Algorithmic Foundations of Robotics XIII","author":"SP Fekete","year":"2020","unstructured":"Fekete, S.P., Gmyr, R., Hugo, S., Keldenich, P., Scheffer, C., Schmidt, A.: CADbots: algorithmic aspects of manipulating programmable matter with finite automata. In: Morales, M., Tapia, L., S\u00e1nchez-Ante, G., Hutchinson, S. (eds.) WAFR 2018. SPAR, vol. 14, pp. 727\u2013743. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-44051-0_42"},{"key":"5_CR17","unstructured":"Fekete, S.P., Niehs, E., Scheffer, C., Schmidt, A.: Connected assembly and reconfiguration by finite automata. CoRR (2019)"},{"key":"5_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/11561071_4","volume-title":"Algorithms \u2013 ESA 2005","author":"R Fleischer","year":"2005","unstructured":"Fleischer, R., Trippen, G.: Exploring an unknown graph efficiently. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 11\u201322. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11561071_4"},{"issue":"3","key":"5_CR19","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":"5_CR20","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Ilcinkas, D.: Digraphs exploration with little memory. In: Symposium on Theoretical Aspects of Computer Science (STACS), pp. 246\u2013257 (2004)","DOI":"10.1007\/978-3-540-24749-4_22"},{"issue":"2\u20133","key":"5_CR21","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. Theor. Comput. Sci. 345(2\u20133), 331\u2013344 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"5_CR22","unstructured":"Gasieniec, L., Pelc, A., Radzik, T., Zhang, X.: Tree exploration with logarithmic memory. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 585\u2013594 (2007)"},{"key":"5_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1007\/978-3-540-92248-3_2","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"L G\u0105sieniec","year":"2008","unstructured":"G\u0105sieniec, L., Radzik, T.: Memory efficient anonymous graph exploration. In: Broersma, H., Erlebach, T., Friedetzky, T., Paulusma, D. (eds.) WG 2008. LNCS, vol. 5344, pp. 14\u201329. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-92248-3_2"},{"key":"5_CR24","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), pp. 52:1\u201352:15 (2018)"},{"key":"5_CR25","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), pp. 122\u2013138 (2018)","DOI":"10.1007\/978-3-030-00030-1_8"},{"key":"5_CR26","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), pp. 9\u201312 (2017)"},{"key":"5_CR27","doi-asserted-by":"crossref","unstructured":"Gregg, C.E., Jenett, B., Cheung, K.C.: Assembled, modular hardware architectures - what price reconfigurability? In: IEEE Aerospace Conference, pp. 1\u201310 (2019)","DOI":"10.1109\/AERO.2019.8741533"},{"issue":"9","key":"5_CR28","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":"4","key":"5_CR29","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. Robots 38(4), 383\u2013413 (2015). https:\/\/doi.org\/10.1007\/s10514-015-9421-8","journal-title":"Auton. Robots"},{"key":"5_CR30","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), pp. 5474\u20135479 (2017)","DOI":"10.1109\/ICRA.2017.7989644"},{"key":"5_CR31","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":"5_CR32","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, p. 1876 (2017)","DOI":"10.2514\/6.2017-1876"},{"issue":"1\u20132","key":"5_CR33","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1007\/s00453-011-9518-1","volume":"63","author":"A Kosowski","year":"2012","unstructured":"Kosowski, A., Navarra, A.: Graph decomposition for memoryless periodic exploration. Algorithmica 63(1\u20132), 26\u201338 (2012)","journal-title":"Algorithmica"},{"key":"5_CR34","doi-asserted-by":"crossref","unstructured":"Niehs, E., et al.: Recognition and reconfiguration of lattice-based cellular structures by simple robots. In: IEEE International Conference on Robotics and Automation (ICRA) (2020, to appear). https:\/\/www.ibr.cs.tu-bs.de\/users\/fekete\/hp\/publications\/PDF\/2020-Automata_ICRA.pdf","DOI":"10.1109\/ICRA40945.2020.9196700"},{"issue":"2","key":"5_CR35","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"},{"key":"5_CR36","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), pp. 353\u2013354 (2013)","DOI":"10.1145\/2422436.2422476"}],"container-title":["Lecture Notes in Computer Science","Algorithms for Sensor Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-62401-9_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,24]],"date-time":"2021-04-24T00:04:04Z","timestamp":1619222644000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-62401-9_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030624002","9783030624019"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-62401-9_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"28 October 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ALGOSENSORS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Pisa","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 September 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 September 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"algosensors2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/algo2020.di.unipi.it\/ALGOSENSORS2020\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"27","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"12","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"44% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.14","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.68","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The conference was held virtually due to the COVID-19 pandemic.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}