{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T22:40:07Z","timestamp":1747867207405,"version":"3.41.0"},"publisher-location":"Cham","reference-count":35,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031917356","type":"print"},{"value":"9783031917363","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-91736-3_5","type":"book-chapter","created":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T22:01:55Z","timestamp":1747864915000},"page":"74-91","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Exploration of\u00a0Convex Terrains by\u00a0a\u00a0Deterministic Automaton with\u00a0Pebbles"],"prefix":"10.1007","author":[{"given":"Mohamed Anouar","family":"Baaziz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrzej","family":"Pelc","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,5,22]]},"reference":[{"key":"5_CR1","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, 1164\u20131188 (2000)","journal-title":"SIAM J. Comput."},{"key":"5_CR2","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/s00453-001-0067-x","volume":"32","author":"S Albers","year":"2002","unstructured":"Albers, S., Kursawe, K., Schuierer, S.: Exploring unknown environments with obstacles. Algorithmica 32, 123\u2013143 (2002)","journal-title":"Algorithmica"},{"issue":"2","key":"5_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., Singh, M.: Piecemeal graph learning by a mobile robot. Inf. Comput. 152(2), 155\u2013172 (1999)","journal-title":"Inf. Comput."},{"key":"5_CR4","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1006\/inco.1993.1054","volume":"106","author":"R Baeza-Yates","year":"1993","unstructured":"Baeza-Yates, R., Culberson, J., Rawlins, J.: Searching the plane. Inf. Comput. 106, 234\u2013252 (1993)","journal-title":"Inf. Comput."},{"issue":"1","key":"5_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.2001.3081","volume":"176","author":"M Bender","year":"2002","unstructured":"Bender, M., Fernandez, A., Ron, D., Sahai, A., Vadhan, S.: The power of a pebble: exploring and mapping directed graphs. Inf. Comput. 176(1), 1\u201321 (2002)","journal-title":"Inf. Comput."},{"key":"5_CR6","doi-asserted-by":"crossref","unstructured":"Bender, M., Slonim, D.: 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)","DOI":"10.1109\/SFCS.1994.365703"},{"key":"5_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 Symposium on Foundations of Computer Science (FOCS), pp. 132\u2013142 (1978)","DOI":"10.1109\/SFCS.1978.30"},{"key":"5_CR8","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/BF00993411","volume":"18","author":"M Betke","year":"1995","unstructured":"Betke, M., Rivest, R., Singh, M.: Piecemeal learning of an unknown environment. Mach. Learn. 18, 231\u2013254 (1995)","journal-title":"Mach. Learn."},{"key":"5_CR9","unstructured":"Bhagat, S., Pelc, A.: Exploring wedges of an oriented grid by an automaton with pebbles. CoRR arxiv:2302.00052 (2023)"},{"key":"5_CR10","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":"5_CR11","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. Nachrichten 86, 195\u2013282 (1978)","journal-title":"Math. Nachrichten"},{"key":"5_CR12","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":"5_CR13","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":"5_CR14","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/j.ic.2013.02.001","volume":"225","author":"J Czyzowicz","year":"2013","unstructured":"Czyzowicz, J., Ilcinkas, D., Labourel, A., Pelc, A.: Worst-case optimal exploration of terrains with obstacles. Inf. Comput. 225, 16\u201328 (2013)","journal-title":"Inf. Comput."},{"key":"5_CR15","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1016\/j.ic.2010.09.005","volume":"209","author":"J Czyzowicz","year":"2011","unstructured":"Czyzowicz, J., Labourel, A., Pelc, A.: Optimality and competitiveness of exploring polygons by mobile robots. Inf. Comput. 209, 74\u201388 (2011)","journal-title":"Inf. Comput."},{"key":"5_CR16","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. 67\u201376 (2010)","DOI":"10.1145\/1835698.1835761"},{"issue":"2","key":"5_CR17","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1145\/274787.274788","volume":"45","author":"X Deng","year":"1998","unstructured":"Deng, X., Kameda, T., Papadimitriou, C.H.: How to learn an unknown environment I: the rectilinear case. J. ACM 45(2), 215\u2013245 (1998)","journal-title":"J. ACM"},{"issue":"3","key":"5_CR18","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"},{"issue":"1","key":"5_CR19","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. Algor. 51(1), 38\u201363 (2004)","journal-title":"J. Algor."},{"key":"5_CR20","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"},{"key":"5_CR21","doi-asserted-by":"crossref","unstructured":"Disser, Y., Hackfeld, J., Klimm, M.: Undirected graph exploration with $$Theta(\\log \\log n)$$ pebbles. In: 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 25\u201339 (2016)","DOI":"10.1137\/1.9781611974331.ch3"},{"issue":"6","key":"5_CR22","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1109\/70.105395","volume":"7","author":"G Dudek","year":"1991","unstructured":"Dudek, G., Jenkins, M., Milios, E., Wilkes, D.: Robotic exploration as graph construction. IEEE Trans. Rob. Autom. 7(6), 859\u2013865 (1991)","journal-title":"IEEE Trans. Rob. Autom."},{"key":"5_CR23","unstructured":"Duncan, C., Kobourov, S., Kumar, V.: Optimal constrained graph exploration. In: 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 807\u2013814 (2001)"},{"key":"5_CR24","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":"5_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/978-3-540-28629-5_34","volume-title":"Mathematical Foundations of Computer Science 2004","author":"P Fraigniaud","year":"2004","unstructured":"Fraigniaud, P., Ilcinkas, D., Peer, G., Pelc, A., Peleg, D.: Graph exploration by a finite automaton. In: Fiala, J., Koubek, V., Kratochv\u00edl, J. (eds.) MFCS 2004. LNCS, vol. 3153, pp. 451\u2013462. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-28629-5_34"},{"key":"5_CR26","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Ilcinkas, D.: Directed graphs exploration with little memory. In: 21st Symposium on Theoretical Aspects of Computer Science (STACS). LNCS 1996, pp. 246\u2013257 (2004)","DOI":"10.1007\/978-3-540-24749-4_22"},{"key":"5_CR27","doi-asserted-by":"crossref","unstructured":"Hemmerling, A.: Labyrinth Problems: Labyrinth-Searching Abilities of Automata. Teubner-Texte zur Mathematik, vol. 114. B. G. Teubner Verlagsgesellschaft, Leipzig (1989)","DOI":"10.1007\/978-3-322-94560-0"},{"key":"5_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/3-540-10854-8_47","volume-title":"Fundamentals of Computation Theory","author":"F Hoffmann","year":"1981","unstructured":"Hoffmann, F.: One pebble does not suffice to search plane labyrinths. In: G\u00e9cseg, F. (ed.) FCT 1981. LNCS, vol. 117, pp. 433\u2013444. Springer, Heidelberg (1981). https:\/\/doi.org\/10.1007\/3-540-10854-8_47"},{"key":"5_CR29","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1137\/S0097539799348670","volume":"31","author":"F Hoffmann","year":"2001","unstructured":"Hoffmann, F., Icking, C., Klein, R., Kriegel, K.: The polygon exploration problem. SIAM J. Comput. 31, 577\u2013600 (2001)","journal-title":"SIAM J. Comput."},{"key":"5_CR30","unstructured":"Kozen, D.: Automata and planar graphs. Fund. Computat. Theory (FCT), 243\u2013254 (1979)"},{"key":"5_CR31","doi-asserted-by":"crossref","unstructured":"Langetepe, E.: On the optimality of spiral search. In: Proceedings of 21st Annual ACM-SIAM Symposium Discrete Algorithm (SODA 2010), pp. 1\u201312 (2010)","DOI":"10.1137\/1.9781611973075.1"},{"issue":"2","key":"5_CR32","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1006\/jagm.1999.1043","volume":"33","author":"P Panaite","year":"1999","unstructured":"Panaite, P., Pelc, A.: Exploring unknown undirected graphs. J. Algor. 33(2), 81\u2013295 (1999)","journal-title":"J. Algor."},{"key":"5_CR33","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":"5_CR34","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/BF00288647","volume":"13","author":"HA Rollik","year":"1980","unstructured":"Rollik, H.A.: Automaten in planaren Graphen. Acta Informatica 13, 287\u2013298 (1980)","journal-title":"Acta Informatica"},{"issue":"4","key":"5_CR35","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":["Lecture Notes in Computer Science","Structural Information and Communication Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-91736-3_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T22:02:09Z","timestamp":1747864929000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-91736-3_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031917356","9783031917363"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-91736-3_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"22 May 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SIROCCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Colloquium on Structural Information and Communication Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Delphi","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Greece","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 June 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 June 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"32","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sirocco2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.torontomu.ca\/sirocco-2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}