{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T10:45:11Z","timestamp":1778496311282,"version":"3.51.4"},"reference-count":13,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2008,8,1]],"date-time":"2008-08-01T00:00:00Z","timestamp":1217548800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2008,8]]},"abstract":"<jats:p>\n            A finite automaton, simply referred to as a\n            <jats:italic>robot<\/jats:italic>\n            , has to explore a graph, that is, visit all the nodes of the graph. The robot has no a priori knowledge of the topology of the graph, nor of its size. It is known that for any\n            <jats:italic>k<\/jats:italic>\n            -state robot, there exists a graph of maximum degree 3 that the robot cannot explore. This article considers the effects of allowing the system designer to add short labels to the graph nodes in a preprocessing stage, for helping the exploration by the robot. We describe an exploration algorithm that, given appropriate 2-bit labels (in fact, only 3-valued labels), allows a robot to explore all graphs. Furthermore, we describe a suitable labeling algorithm for generating the required labels in linear time. We also show how to modify our labeling scheme so that a robot can explore all graphs of bounded degree, given appropriate 1-bit labels. In other words, although there is no robot able to explore all graphs of maximum degree 3, there is a robot R, and a way to color in black or white the nodes of any bounded-degree graph\n            <jats:italic>G<\/jats:italic>\n            , so that R can explore the colored graph\n            <jats:italic>G<\/jats:italic>\n            . Finally, we give impossibility results regarding graph exploration by a robot with no internal memory (i.e., a single-state automaton).\n          <\/jats:p>","DOI":"10.1145\/1383369.1383373","type":"journal-article","created":{"date-parts":[[2008,8,27]],"date-time":"2008-08-27T11:56:36Z","timestamp":1219838196000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":73,"title":["Label-guided graph exploration by a finite automaton"],"prefix":"10.1145","volume":"4","author":[{"given":"Reuven","family":"Cohen","sequence":"first","affiliation":[{"name":"Boston University, Boston, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pierre","family":"Fraigniaud","sequence":"additional","affiliation":[{"name":"CNRS and Universit\u00e9 Paris Diderot, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Ilcinkas","sequence":"additional","affiliation":[{"name":"CNRS and Universit\u00e9 Bordeaux I, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amos","family":"Korman","sequence":"additional","affiliation":[{"name":"CNRS and Universit\u00e9 Paris Diderot, Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Peleg","sequence":"additional","affiliation":[{"name":"The Weizmann Institute, Rehovot, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,8,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1978.30"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Budach L. 1978. Automata and labyrinths. Math. Nachrichten 195--282.  Budach L. 1978. Automata and labyrinths. Math. Nachrichten 195--282.","DOI":"10.1002\/mana.19780860120"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.10.002"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.07.014"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146410"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/11429647_13"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1248377.1248402"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 585--594","author":"Gasieniec L","unstructured":"Gasieniec , L , Pelc , A , Radzik , T , and Zhang , X . 2007. Tree exploration with logarithmic memory . In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 585--594 . Gasieniec, L, Pelc, A, Radzik, T, and Zhang, X. 2007. Tree exploration with logarithmic memory. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 585--594."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073814.1073817"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the Conference on Fundamentals of Computation Theory (FCT), 243--254","author":"Kozen D.","year":"1979","unstructured":"Kozen , D. 1979 . Automata and planar graphs . In Proceedings of the Conference on Fundamentals of Computation Theory (FCT), 243--254 . Kozen, D. 1979. Automata and planar graphs. In Proceedings of the Conference on Fundamentals of Computation Theory (FCT), 243--254."},{"key":"e_1_2_1_11_1","unstructured":"Rabin M. O. 1967. Maze threading automata. In a seminar talk presented at the University of California at Berkeley.  Rabin M. O. 1967. Maze threading automata. In a seminar talk presented at the University of California at Berkeley."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/647209.719876"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 8th Conference of the Josiah Macy Jr. Foundation (Cybernetics), 173--180","author":"Shannon C. E.","year":"1951","unstructured":"Shannon , C. E. 1951 . Presentation of a maze-solving machine . In Proceedings of the 8th Conference of the Josiah Macy Jr. Foundation (Cybernetics), 173--180 . Shannon, C. E. 1951. Presentation of a maze-solving machine. In Proceedings of the 8th Conference of the Josiah Macy Jr. Foundation (Cybernetics), 173--180."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1383369.1383373","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1383369.1383373","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:57:46Z","timestamp":1750255066000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1383369.1383373"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8]]},"references-count":13,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,8]]}},"alternative-id":["10.1145\/1383369.1383373"],"URL":"https:\/\/doi.org\/10.1145\/1383369.1383373","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,8]]},"assertion":[{"value":"2006-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-08-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}