{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,24]],"date-time":"2026-05-24T06:04:58Z","timestamp":1779602698748,"version":"3.53.1"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032264640","type":"print"},{"value":"9783032264657","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"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":[[2026]]},"DOI":"10.1007\/978-3-032-26465-7_14","type":"book-chapter","created":{"date-parts":[[2026,5,24]],"date-time":"2026-05-24T05:48:22Z","timestamp":1779601702000},"page":"253-271","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Cow Path by\u00a0Finite Agent: Time vs Pebbles"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0914-2983","authenticated-orcid":false,"given":"Stefan","family":"Dobrev","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1121-1009","authenticated-orcid":false,"given":"Rastislav","family":"Kr\u00e1lovi\u010d","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-9719-9259","authenticated-orcid":false,"given":"Richard","family":"Kr\u00e1lovi\u010d","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9383-8117","authenticated-orcid":false,"given":"Dana","family":"Pardubsk\u00e1","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0177-8028","authenticated-orcid":false,"given":"Peter","family":"Rossmanith","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,5,24]]},"reference":[{"key":"14_CR1","volume-title":"The Theory of Search Games and Rendezvous","author":"S Alpern","year":"2006","unstructured":"Alpern, S., Gal, S.: The Theory of Search Games and Rendezvous. International Series in Operations Research & Management Science. Springer, US (2006)"},{"key":"14_CR2","doi-asserted-by":"crossref","unstructured":"Baezayates, R.A., Culberson, J.C., Rawlins, G.J.: Searching in the plane. Inform. Comput. 106(2), 234\u2013252 (1993)","DOI":"10.1006\/inco.1993.1054"},{"issue":"4","key":"14_CR3","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/BF02759737","volume":"2","author":"A Beck","year":"1964","unstructured":"Beck, A.: On the linear search problem. Israel J. Math. 2(4), 221\u2013228 (1964)","journal-title":"Israel J. Math."},{"issue":"4","key":"14_CR4","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/BF02798690","volume":"8","author":"A Beck","year":"1970","unstructured":"Beck, A., Newmann, D.J.: Yet more on the linear search problem. Israel J. Math. 8(4), 419\u2013429 (1970)","journal-title":"Israel J. Math."},{"issue":"3","key":"14_CR5","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1137\/1005070","volume":"5","author":"R Bellman","year":"1963","unstructured":"Bellman, R.: Problem 63\u20139, an optimal search. SIAM Rev. 5(3), 274\u2013274 (1963)","journal-title":"SIAM Rev."},{"issue":"1","key":"14_CR6","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.: The power of a pebble: exploring and mapping directed graphs. Inf. Comput. 176(1), 1\u201321 (2002)","journal-title":"Inf. Comput."},{"key":"14_CR7","doi-asserted-by":"crossref","unstructured":"Bhattacharya, A., Gorain, B., Mandal, P.S.: Treasure hunt in graph using pebbles. In: Devismes, S., Petit, F., Altisen, K., \u00a0Di Luna, G.A., Anta, A.F., eds., Stabilization, Safety, and Security of Distributed Systems - 24th International Symposium, SSS 2022, Clermont-Ferrand, France, November 15-17, 2022, Proceedings, volume 13751 of LNCS, pp. 99\u2013113. Springer (2022)","DOI":"10.1007\/978-3-031-21017-4_7"},{"key":"14_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: 19th Annual Symposium on Foundations of Computer Science, Ann Arbor, Michigan, USA, 16-18 October 1978, pp. 132\u2013142. IEEE Computer Society (1978)","DOI":"10.1109\/SFCS.1978.30"},{"key":"14_CR9","doi-asserted-by":"crossref","unstructured":"Bollig, B., Gastin, P., Monmege, B., Zeitoun, M.: Logical characterization of weighted pebble walking automata. In: Henzinger, T.A., Miller, D., eds., Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM\/IEEE Symposium on Logic in Computer Science (LICS), CSL-LICS \u201914, Vienna, Austria, July 14\u201318, 2014, pp. 19:1\u201319:10. ACM, (2014)","DOI":"10.1145\/2603088.2603118"},{"key":"14_CR10","doi-asserted-by":"crossref","unstructured":"Chang, J.H., Ibarra, O.H., Palis, M.A., Ravikumar, B.: On pebble automata. Theor. Comput. Sci. 44, 111\u2013121, (1986)","DOI":"10.1016\/0304-3975(86)90112-X"},{"key":"14_CR11","doi-asserted-by":"crossref","unstructured":"Cohen, L., Emek, Y., Louidor, O., Uitto, J.: Exploring an infinite space with finite memory scouts. In: Klein, P.N., ed., Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pp. 207\u2013224. SIAM (2017)","DOI":"10.1137\/1.9781611974782.14"},{"key":"14_CR12","doi-asserted-by":"crossref","unstructured":"Das, S.K., Dhar, A.K., Gorain, B., Mahawar, M.: Collision-free exploration by mobile agents using pebbles. In: Korman, A., Chakraborty, S., Peri, S., Boldrini, C., Robinson, P., eds., Proceedings of the 26th International Conference on Distributed Computing and Networking, ICDCN 2025, Hyderabad, India, January 4\u20137, 2025, pp. 161\u2013170. ACM (2025)","DOI":"10.1145\/3700838.3700863"},{"issue":"1","key":"14_CR13","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":"14_CR14","doi-asserted-by":"crossref","unstructured":"Disser, Y., Hackfeld, J., Klimm, M.: Undirected graph exploration with $$\\theta (\\log \\log n)$$ pebbles. In: Krauthgamer, R., ed., Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pp. 25\u201339. SIAM (2016)","DOI":"10.1137\/1.9781611974331.ch3"},{"key":"14_CR15","doi-asserted-by":"crossref","unstructured":"Disser, Y., Hackfeld, J., Klimm, M.: Tight bounds for undirected graph exploration with pebbles and multiple agents. J. ACM, 66(6), 40:1\u201340:41 (2019)","DOI":"10.1145\/3356883"},{"key":"14_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-3-540-72951-8_5","volume-title":"Structural Information and Communication Complexity","author":"M Dynia","year":"2007","unstructured":"Dynia, M., \u0141opusza\u0144ski, J., Schindelhauer, C.: Why robots need maps. In: Prencipe, G., Zaks, S. (eds.) SIROCCO 2007. LNCS, vol. 4474, pp. 41\u201350. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-72951-8_5"},{"key":"14_CR17","doi-asserted-by":"crossref","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). Structural Information and Communication Complexity","DOI":"10.1016\/j.tcs.2015.05.054"},{"key":"14_CR18","unstructured":"Euler, L.: Solutio problematis ad geometriam situs pertinentis. Commentarii Academiae Scientiarum Imperialis Petropolitanae 8 128\u2013140 (1736)"},{"key":"14_CR19","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"},{"key":"14_CR20","doi-asserted-by":"crossref","unstructured":"Flocchini, P., Prencipe, G., Santoro, N.: Distributed computing by mobile entities, Current Research in Moving and Computing, vol. 11340 LNCS. Springer (2019)","DOI":"10.1007\/978-3-030-11072-7"},{"issue":"2\u20133","key":"14_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."},{"issue":"1","key":"14_CR22","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/BF02764811","volume":"12","author":"S Gal","year":"1972","unstructured":"Gal, S.: A general search game. Israel J. Math. 12(1), 32\u201345 (1972)","journal-title":"Israel J. Math."},{"key":"14_CR23","unstructured":"Gal, S.: Search Games. Mathematics in science and engineering : a series of monographs and textbooks. Academic Press (1980)"},{"key":"14_CR24","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.tcs.2022.04.011","volume":"922","author":"B Gorain","year":"2022","unstructured":"Gorain, B., Mondal, K., Nayak, H., Pandit, S.: Pebble guided optimal treasure hunt in anonymous graphs. Theor. Comput. Sci. 922, 61\u201380 (2022)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"14_CR25","doi-asserted-by":"publisher","first-page":"808","DOI":"10.1016\/j.jcss.2007.09.004","volume":"74","author":"L G\u0105sieniec","year":"2008","unstructured":"G\u0105sieniec, L., Klasing, R., Martin, R., Navarra, A., Zhang, X.: Fast periodic graph exploration with constant memory. J. Comput. Syst. Sci. 74(5), 808\u2013822 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"14_CR26","volume-title":"Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit","author":"R Isaacs","year":"1965","unstructured":"Isaacs, R.: Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit. Control and Optimization. Dover books on mathematics, Wiley (1965)"},{"issue":"1","key":"14_CR27","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1006\/inco.1996.0092","volume":"131","author":"M-Y Kao","year":"1996","unstructured":"Kao, M.-Y., Reif, J.H., Tate, S.R.: Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem. Inf. Comput. 131(1), 63\u201379 (1996)","journal-title":"Inf. Comput."},{"key":"14_CR28","doi-asserted-by":"crossref","unstructured":"Martynova, O., Okhotin, A.: A time to cast away stones. In: Nagy, B., ed., Implementation and Application of Automata - 27th International Conference, CIAA 2023, Famagusta, North Cyprus, September 19-22, 2023, Proceedings, vol. 14151 of LNCS, pp. 242\u2013253. Springer (2023)","DOI":"10.1007\/978-3-031-40247-0_18"},{"issue":"1","key":"14_CR29","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0304-3975(91)90263-2","volume":"84","author":"CH Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Shortest paths without a map. Theor. Comput. Sci. 84(1), 127\u2013150 (1991)","journal-title":"Theor. Comput. Sci."},{"key":"14_CR30","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/j.dam.2024.05.024","volume":"356","author":"D Pattanayak","year":"2024","unstructured":"Pattanayak, D., Pelc, A.: Graph exploration by a deterministic memoryless automaton with pebbles. Discret. Appl. Math. 356, 149\u2013160 (2024)","journal-title":"Discret. Appl. Math."},{"key":"14_CR31","doi-asserted-by":"crossref","unstructured":"Rosenkrantz, D.J., Stearns, R.E., Lewis II, P.M.: An analysis of several heuristics for the traveling salesman problem. SIAM J. Comput. 6(3), 563\u2013581 (1977)","DOI":"10.1137\/0206041"}],"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-032-26465-7_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,24]],"date-time":"2026-05-24T05:48:25Z","timestamp":1779601705000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-26465-7_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032264640","9783032264657"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-26465-7_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"24 May 2026","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":"Durham","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"United Kingdom","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 June 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 June 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"33","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sirocco2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sirocco2026.webspace.durham.ac.uk\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}