{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,26]],"date-time":"2025-11-26T16:34:27Z","timestamp":1764174867558,"version":"3.37.3"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,7,25]],"date-time":"2020-07-25T00:00:00Z","timestamp":1595635200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,7,25]],"date-time":"2020-07-25T00:00:00Z","timestamp":1595635200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["2018-03899"],"award-info":[{"award-number":["2018-03899"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2015\/17\/B\/ST6\/01887"],"award-info":[{"award-number":["2015\/17\/B\/ST6\/01887"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A robot modeled as a deterministic finite automaton has to build a structure from material available to it. The robot navigates in the infinite oriented grid <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathbb {Z}} \\times {\\mathbb {Z}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>Z<\/mml:mi>\n                    <mml:mo>\u00d7<\/mml:mo>\n                    <mml:mi>Z<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Some cells of the grid are full (contain a brick) and others are empty. The subgraph of the grid induced by full cells, called the <jats:italic>shape<\/jats:italic>, is initially connected. The (Manhattan) distance between the furthest cells of the shape is called its <jats:italic>span<\/jats:italic>. The robot starts at a full cell. It can carry at most one brick at a time. At each step it can pick a brick from a full cell, move to an adjacent cell and drop a brick at an empty cell. The aim of the robot is to construct the most compact possible structure composed of all bricks, i.e., a <jats:italic>nest<\/jats:italic>. That is, the robot has to move all bricks in such a way that the span of the resulting shape be the smallest. Our main result is the design of a deterministic finite automaton that accomplishes this task and subsequently stops, for every initially connected shape, in time <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(sn)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>s<\/mml:mi>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where <jats:italic>s<\/jats:italic> is the span of the initial shape and <jats:inline-formula><jats:alternatives><jats:tex-math>$$n$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>n<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is the number of bricks. We show that this complexity is optimal.<\/jats:p>","DOI":"10.1007\/s00453-020-00752-0","type":"journal-article","created":{"date-parts":[[2020,7,25]],"date-time":"2020-07-25T05:29:17Z","timestamp":1595654957000},"page":"144-176","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Building a Nest by an Automaton"],"prefix":"10.1007","volume":"83","author":[{"given":"Jurek","family":"Czyzowicz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4000-4818","authenticated-orcid":false,"given":"Dariusz","family":"Dereniowski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrzej","family":"Pelc","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,7,25]]},"reference":[{"key":"752_CR1","unstructured":"Akitaya, H.A., Arkin, E.M., Damian, M., Demaine, E.D., Dujmovic, V., Flatland, R.Y., Korman, M., Palop, B., Parada, I., van Renssen, A., Sacrist\u00e1n, V.: Universal reconfiguration of facet-connected modular robots by pivots: the O(1) musketeers. In: 27th Annual European Symposium on Algorithms, ESA 2019, September 9\u201311, 2019, Munich\/Garching, Germany, pp. 3:1\u20133:14 (2019)"},{"issue":"4","key":"752_CR2","doi-asserted-by":"publisher","first-page":"1164","DOI":"10.1137\/S009753979732428X","volume":"29","author":"S Albers","year":"2000","unstructured":"Albers, S., Henzinger, M.R.: Exploring unknown environments. SIAM J. Comput. 29(4), 1164\u20131188 (2000)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"752_CR3","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1006\/inco.1999.2795","volume":"152","author":"B Awerbuch","year":"1999","unstructured":"Awerbuch, B., Betke, M., Rivest, R.L., Singh, M.: Piecemeal graph exploration by a mobile robot. Inf. Comput. 152(2), 155\u2013172 (1999)","journal-title":"Inf. Comput."},{"issue":"1","key":"752_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.2001.3081","volume":"176","author":"MA Bender","year":"2002","unstructured":"Bender, M.A., Fern\u00e1ndez, A., Ron, D., Sahai, A., Vadhan, S.P.: The power of a pebble: exploring and mapping directed graphs. Inf. Comput. 176(1), 1\u201321 (2002)","journal-title":"Inf. Comput."},{"key":"752_CR5","unstructured":"Bender, M.A., Slonim, D.K.: The power of team exploration: two robots can learn unlabeled directed graphs. In: 35th Annual Symposium on Foundations of Computer Science (FOCS), pp. 75\u201385 (1994)"},{"issue":"2\u20133","key":"752_CR6","first-page":"231","volume":"18","author":"M Betke","year":"1995","unstructured":"Betke, M., Rivest, R.L., Singh, M.: Piecemeal learning of an unknown environment. Mach. Learn. 18(2\u20133), 231\u2013254 (1995)","journal-title":"Mach. Learn."},{"key":"752_CR7","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: 19th Annual Symposium on Foundations of Computer Science (FOCS), pp. 132\u2013142 (1978)","DOI":"10.1109\/SFCS.1978.30"},{"key":"752_CR8","unstructured":"Brandt, S., Uitto, J., Wattenhofer, R.: A tight lower bound for semi-synchronous collaborative grid exploration. In: 32nd International Symposium on Distributed Computing (DISC), pp. 13:1\u201313:17 (2018)"},{"key":"752_CR9","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1002\/mana.19780860120","volume":"86","author":"L Budach","year":"1978","unstructured":"Budach, L.: Automata and labyrinths. Math. Nachr. 86, 195\u2013282 (1978)","journal-title":"Math. Nachr."},{"key":"752_CR10","doi-asserted-by":"crossref","unstructured":"Chalopin, J., Das, S., Kosowski, A.: Constructing a map of an anonymous graph: applications of universal sequences. In: 14th International Conference on Principles of Distributed Systems (OPODIS), pp. 119\u2013134 (2010)","DOI":"10.1007\/978-3-642-17653-1_10"},{"key":"752_CR11","doi-asserted-by":"crossref","unstructured":"Cohen, L., Emek, Y., Louidor, O., Uitto, J.: Exploring an infinite space with finite memory scouts. In: 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 207\u2013224 (2017)","DOI":"10.1137\/1.9781611974782.14"},{"key":"752_CR12","doi-asserted-by":"crossref","unstructured":"Das, S., Flocchini, P., Santoro, N., Yamashita, M.: On the computational power of oblivious robots: forming a series of geometric patterns. In: 29th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 267\u2013276 (2010)","DOI":"10.1145\/1835698.1835761"},{"issue":"1","key":"752_CR13","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/s11047-017-9658-6","volume":"17","author":"JJ Daymude","year":"2018","unstructured":"Daymude, J.J., Derakhshandeh, Z., Gmyr, R., Porter, A., Richa, A.W., Scheideler, C., Strothmann, T.: On the runtime of universal coating for programmable matter. Nat. Comput. 17(1), 81\u201396 (2018)","journal-title":"Nat. Comput."},{"key":"752_CR14","unstructured":"Daymude, J.J., Gmyr, R., Hinnenthal, K., Kostitsyna, I., Scheideler, C., Richa, A.W.: Convex hull formation for programmable matter. CoRR, abs\/1805.06149 (2018)"},{"key":"752_CR15","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: Algorithms for Sensor Systems\u201413th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2017, Vienna, Austria, September 7-8, 2017, Revised Selected Papers, pp. 127\u2013140 (2017)","DOI":"10.1007\/978-3-319-72751-6_10"},{"key":"752_CR16","first-page":"615","volume-title":"Computing by Programmable Particles","author":"JJ Daymude","year":"2019","unstructured":"Daymude, J.J., Hinnenthal, K., Richa, A.W., Scheideler, C.: Computing by Programmable Particles, pp. 615\u2013681. Springer, Cham (2019)"},{"issue":"3","key":"752_CR17","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1002\/(SICI)1097-0118(199911)32:3<265::AID-JGT6>3.0.CO;2-8","volume":"32","author":"X Deng","year":"1999","unstructured":"Deng, X., Papadimitriou, C.H.: Exploring an unknown graph. J. Graph Theory 32(3), 265\u2013297 (1999)","journal-title":"J. Graph Theory"},{"key":"752_CR18","doi-asserted-by":"crossref","unstructured":"Derakhshandeh, Z., Dolev, S., Gmyr, R., Richa, A.W., Scheideler, C., Strothmann, T.: Brief announcement: amoebot\u2014a new model for programmable matter. In: 26th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA \u201914, Prague, Czech Republic\u2014June 23\u201325, 2014, pp. 220\u2013222 (2014)","DOI":"10.1145\/2612669.2612712"},{"key":"752_CR19","doi-asserted-by":"crossref","unstructured":"Derakhshandeh, Z., Gmyr, R., Richa, A.W., Scheideler, C., Strothmann, T.: Universal shape formation for programmable matter. In: Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2016, Asilomar State Beach\/Pacific Grove, CA, USA, July 11\u201313, 2016, pp. 289\u2013299 (2016)","DOI":"10.1145\/2935764.2935784"},{"issue":"1","key":"752_CR20","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."},{"key":"752_CR21","doi-asserted-by":"crossref","unstructured":"Dieudonn\u00e9, Y., Petit, F., Villain, V.: Leader election problem versus pattern formation problem. In: 24th International Symposium on Distributed Computing (DISC), pp. 267\u2013281 (2010)","DOI":"10.1007\/978-3-642-15763-9_26"},{"issue":"1","key":"752_CR22","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"},{"issue":"6","key":"752_CR23","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1109\/70.105395","volume":"7","author":"G Dudek","year":"1991","unstructured":"Dudek, G., Jenkin, M., Milios, E.E., Wilkes, D.: Robotic exploration as graph construction. IEEE Trans. Robot. Autom. 7(6), 859\u2013865 (1991)","journal-title":"IEEE Trans. Robot. Autom."},{"issue":"3","key":"752_CR24","doi-asserted-by":"publisher","first-page":"380","DOI":"10.1145\/1159892.1159897","volume":"2","author":"CA Duncan","year":"2006","unstructured":"Duncan, C.A., Kobourov, S.G., Anil Kumar, V.S.: Optimal constrained graph exploration. ACM Trans. Algorithms 2(3), 380\u2013402 (2006)","journal-title":"ACM Trans. Algorithms"},{"key":"752_CR25","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/j.tcs.2015.05.054","volume":"608","author":"Y Emek","year":"2015","unstructured":"Emek, Y., Langner, T., Stolz, D., Uitto, J., Wattenhofer, R.: How many ants does it take to find the food? Theor. Comput. Sci. 608, 255\u2013267 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"752_CR26","unstructured":"Fekete, S.P., Gmyr, R., Hugo, S., Keldenich, P., Scheffer, C., Schmidt, A.: Cadbots: algorithmic aspects of manipulating programmable matter with finite automata. arXiv, arXiv:1810.06360 (2018)"},{"key":"752_CR27","unstructured":"Fekete, S.P., Niehs, E., Scheffer, C., Schmidt, A.: Connected assembly and reconfiguration by finite automata. arXiv, arXiv:1909.03880 (2019)"},{"key":"752_CR28","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Ilcinkas, D.: Digraphs exploration with little memory. In: 21st Annual 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":"752_CR29","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":"752_CR30","unstructured":"Gmyr, R., Hinnenthal, K., Kostitsyna, I., Kuhn, F., Rudolph, D., Scheideler, C.: Shape recognition by a finite automaton robot. In: 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27\u201331, 2018, Liverpool, UK, pp. 52:1\u201352:15 (2018)"},{"key":"752_CR31","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: 24th International Conference on Computing and Molecular Programming (DNA), pp. 122\u2013138 (2018)","DOI":"10.1007\/978-3-030-00030-1_8"},{"key":"752_CR32","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1007\/978-3-322-94560-0","volume-title":"Labyrinth Problems: Labyrinth-Searching Abilities of Automata. Teubner-Texte zur Mathematik","author":"A Hemmerling","year":"1989","unstructured":"Hemmerling, A.: Labyrinth Problems: Labyrinth-Searching Abilities of Automata. Teubner-Texte zur Mathematik, p. 114. B. G. Teubner Verlagsgesellschaft, Leipzig (1989)"},{"key":"752_CR33","doi-asserted-by":"crossref","unstructured":"Hoffmann, F.: One pebble does not suffice to search plane labyrinths. In Fundamentals of Computation Theory (FCT), pp. 433\u2013444 (1981)","DOI":"10.1007\/3-540-10854-8_47"},{"key":"752_CR34","unstructured":"Kozen, D.: Automata and planar graphs. In: Fundamentals of Computation Theory (FCT), pp. 243\u2013254 (1979)"},{"key":"752_CR35","unstructured":"Langner, T., Keller, B., Uitto, J., Wattenhofer, R.: Overcoming obstacles with ants. In: 19th International Conference on Principles of Distributed Systems (OPODIS), pp. 9:1\u20139:17 (2015)"},{"key":"752_CR36","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/j.jcss.2018.12.001","volume":"102","author":"O Michail","year":"2019","unstructured":"Michail, O., Skretas, G., Spirakis, P.G.: On the transformation capability of feasible mechanisms for programmable matter. J. Comput. Syst. Sci. 102, 18\u201339 (2019)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"752_CR37","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":"752_CR38","doi-asserted-by":"crossref","unstructured":"Rao, N., Kareti, S., Shi, W., Iyengar, S.: Robot navigation in unknown terrains: introductory survey of non-heuristic algorithms. Technical report ORNL\/TM-12410, Oak Ridge National Lab. (1993)","DOI":"10.2172\/10180101"},{"key":"752_CR39","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/BF00288647","volume":"13","author":"H-A Rollik","year":"1980","unstructured":"Rollik, H.-A.: Automaten in planaren graphen. Acta Inform. 13, 287\u2013298 (1980)","journal-title":"Acta Inform."},{"issue":"4","key":"752_CR40","doi-asserted-by":"publisher","first-page":"1347","DOI":"10.1137\/S009753979628292X","volume":"28","author":"I Suzuki","year":"1999","unstructured":"Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots: formation of geometric patterns. SIAM J. Comput. 28(4), 1347\u20131363 (1999)","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00752-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00752-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00752-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,24]],"date-time":"2021-07-24T23:30:34Z","timestamp":1627169434000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00752-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,25]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["752"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00752-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2020,7,25]]},"assertion":[{"value":"19 September 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 July 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 July 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}