{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T04:45:03Z","timestamp":1768884303555,"version":"3.49.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2020,2,3]],"date-time":"2020-02-03T00:00:00Z","timestamp":1580688000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,2,3]],"date-time":"2020-02-03T00:00:00Z","timestamp":1580688000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002666","name":"Aalto University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100002666","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Recently, there has been a growing interest in grid exploration by agents with limited capabilities. We show that the grid cannot be explored by three semi-synchronous finite automata, answering an open question by Emek et al. (Theor Comput Sci 608:255\u2013267, 2015) in the negative. In the setting we consider, time is divided into discrete steps, where in each step, an adversarially selected subset of the agents executes one look\u2013compute\u2013move cycle. The agents operate according to a shared finite automaton, where every agent is allowed to have a distinct initial state. The only means of communication is to sense the states of the agents sharing the same grid cell. The agents are equipped with a global compass and whenever an agent moves, the destination cell of the movement is chosen by the agent\u2019s automaton from the set of neighboring grid cells. In contrast to the four agent protocol by Emek et al., we show that three agents do not suffice for grid exploration.<\/jats:p>","DOI":"10.1007\/s00446-020-00369-0","type":"journal-article","created":{"date-parts":[[2020,2,3]],"date-time":"2020-02-03T20:03:41Z","timestamp":1580760221000},"page":"471-484","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A tight lower bound for semi-synchronous collaborative grid exploration"],"prefix":"10.1007","volume":"33","author":[{"given":"Sebastian","family":"Brandt","sequence":"first","affiliation":[]},{"given":"Jara","family":"Uitto","sequence":"additional","affiliation":[]},{"given":"Roger","family":"Wattenhofer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,2,3]]},"reference":[{"key":"369_CR1","doi-asserted-by":"publisher","first-page":"1164","DOI":"10.1137\/S009753979732428X","volume":"29","author":"S Albers","year":"2000","unstructured":"Albers, S., Henzinger, M.: Exploring unknown environments. SIAM J. Comput. 29, 1164\u20131188 (2000)","journal-title":"SIAM J. Comput."},{"key":"369_CR2","doi-asserted-by":"crossref","unstructured":"Aleliunas, R., Karp, R.M., Lipton, R.J., Lovasz, L., Rackoff, C.: Random walks, universal traversal sequences, and the complexity of maze problems. In: FOCS, pp. 218\u2013223 (1979)","DOI":"10.1109\/SFCS.1979.34"},{"issue":"1\u20132","key":"369_CR3","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/0166-218X(95)00054-U","volume":"68","author":"I Averbakh","year":"1996","unstructured":"Averbakh, I., Berman, O.: A heuristic with worst-case analysis for minimax routing of two travelling salesmen on a tree. Discrete Appl. Math. 68(1\u20132), 17\u201332 (1996)","journal-title":"Discrete Appl. Math."},{"key":"369_CR4","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1006\/inco.1993.1054","volume":"106","author":"RA Baeza-Yates","year":"1993","unstructured":"Baeza-Yates, R.A., Culberson, J.C., Rawlins, G.J.E.: Searching in the plane. Inf. Comput. 106, 234\u2013252 (1993)","journal-title":"Inf. Comput."},{"key":"369_CR5","unstructured":"Bender, M.A., Slonim, D.K.: The power of team exploration: two robots can learn unlabeled directed graphs. In: FOCS, pp. 75\u201385 (1994)"},{"key":"369_CR6","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: FOCS, pp. 132\u2013142 (1978)","DOI":"10.1109\/SFCS.1978.30"},{"key":"369_CR7","doi-asserted-by":"crossref","unstructured":"Blum, M., Sakoda, W.J.: On the capability of finite automata in 2 and 3 dimensional space. In: FOCS, pp. 147\u2013161 (1977)","DOI":"10.1109\/SFCS.1977.20"},{"issue":"1","key":"369_CR8","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(1), 195\u2013282 (1978)","journal-title":"Math. Nachr."},{"key":"369_CR9","first-page":"164","volume-title":"Group Search on the Line","author":"M Chrobak","year":"2015","unstructured":"Chrobak, M., Gasieniec, L., Gorry, T., Martin, R.: Group Search on the Line, pp. 164\u2013176. Springer, Berlin (2015)"},{"key":"369_CR10","doi-asserted-by":"crossref","unstructured":"Cohen, L., Emek, Y., Louidor, O., Uitto, J.: Exploring an infinite space with finite memory scouts. In: SODA, pp. 207\u2013224 (2017)","DOI":"10.1137\/1.9781611974782.14"},{"key":"369_CR11","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.: Exploring an unknown graph. J. Graph Theory 32, 265\u2013297 (1999)","journal-title":"J. Graph Theory"},{"key":"369_CR12","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, 38\u201363 (2004)","journal-title":"J. Algorithms"},{"key":"369_CR13","doi-asserted-by":"crossref","unstructured":"Disser, Y., Hackfeld, J., Klimm, M.: Undirected graph exploration with $$\\Theta (\\log \\log n)$$ pebbles. In: SODA, pp. 25\u201339 (2016)","DOI":"10.1137\/1.9781611974331.ch3"},{"issue":"3","key":"369_CR14","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., Kumar, V.S.A.: Optimal constrained graph exploration. ACM Trans. Algorithms 2(3), 380\u2013402 (2006)","journal-title":"ACM Trans. Algorithms"},{"key":"369_CR15","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). https:\/\/doi.org\/10.1016\/j.tcs.2015.05.054","journal-title":"Theor. Comput. Sci."},{"key":"369_CR16","doi-asserted-by":"crossref","unstructured":"Emek, Y., Langner, T., Uitto, J., Wattenhofer, R.: Solving the ANTS problem with asynchronous finite state machines. In: ICALP, pp. 471\u2013482 (2014)","DOI":"10.1007\/978-3-662-43951-7_40"},{"key":"369_CR17","doi-asserted-by":"crossref","unstructured":"Feinerman, O., Korman, A., Lotker, Z., Sereni, J.S.: Collaborative search on the plane without communication. In: PODC, pp. 77\u201386 (2012)","DOI":"10.1145\/2332432.2332444"},{"key":"369_CR18","unstructured":"Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Distributed coordination of a set of autonomous mobile robots. In: Intelligent Vehicles Symposium, pp. 480\u2013485 (2000)"},{"key":"369_CR19","first-page":"246","volume-title":"Digraphs Exploration with Little Memory","author":"P Fraigniaud","year":"2004","unstructured":"Fraigniaud, P., Ilcinkas, D.: Digraphs Exploration with Little Memory, pp. 246\u2013257. Springer, Berlin (2004)"},{"key":"369_CR20","doi-asserted-by":"crossref","unstructured":"Hoffmann, F.: One pebble does not suffice to search plane labyrinths. In: FCT, pp. 433\u2013444 (1981)","DOI":"10.1007\/3-540-10854-8_47"},{"key":"369_CR21","unstructured":"L\u00f3pez-Ortiz, A., Sweet, G.: Parallel searching on a lattice. In: CCCG, pp. 125\u2013128 (2001)"},{"key":"369_CR22","unstructured":"Panaite, P., Pelc, A.: Exploring unknown undirected graphs. In: SODA, pp. 316\u2013322 (1998)"},{"key":"369_CR23","first-page":"266","volume-title":"Automaten in Planaren Graphen","author":"HA Rollik","year":"1979","unstructured":"Rollik, H.A.: Automaten in Planaren Graphen, pp. 266\u2013275. Springer, Berlin (1979)"},{"issue":"3","key":"369_CR24","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1002\/(SICI)1097-4563(199603)13:3<127::AID-ROB1>3.0.CO;2-U","volume":"13","author":"K Sugihara","year":"1996","unstructured":"Sugihara, K., Suzuki, I.: Distributed algorithms for formation of geometric patterns with many mobile robots. J. Robot. Syst. 13(3), 127\u2013139 (1996)","journal-title":"J. Robot. Syst."},{"issue":"4","key":"369_CR25","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."},{"key":"369_CR26","doi-asserted-by":"crossref","unstructured":"Suzuki, I., Yarnashita, M.: Distributed anonymous mobile robots\u2014formation and agreement problems. In: SIROCCO, pp. 1347\u20131363 (1996)","DOI":"10.1137\/S009753979628292X"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-020-00369-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-020-00369-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-020-00369-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,2]],"date-time":"2021-02-02T01:02:00Z","timestamp":1612227720000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-020-00369-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,3]]},"references-count":26,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["369"],"URL":"https:\/\/doi.org\/10.1007\/s00446-020-00369-0","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,2,3]]},"assertion":[{"value":"4 July 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 January 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 February 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}