{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,16]],"date-time":"2026-09-16T08:34:18Z","timestamp":1789547658693,"version":"build-2803163510"},"publisher-location":"Berlin, Heidelberg","reference-count":38,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642293436","type":"print"},{"value":"9783642293443","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-29344-3_31","type":"book-chapter","created":{"date-parts":[[2012,4,10]],"date-time":"2012-04-10T14:19:29Z","timestamp":1334067569000},"page":"362-374","source":"Crossref","is-referenced-by-count":12,"title":["Decidability Classes for Mobile Agents\u00a0Computing"],"prefix":"10.1007","author":[{"given":"Pierre","family":"Fraigniaud","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrzej","family":"Pelc","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"31_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 Journal on Computing\u00a029, 1164\u20131188 (2000)","journal-title":"SIAM Journal on Computing"},{"key":"31_CR2","doi-asserted-by":"crossref","unstructured":"Angluin, D.: Local and global properties in networks of processors. In: STOC 1980, pp. 82\u201393 (1980)","DOI":"10.1145\/800141.804655"},{"key":"31_CR3","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1002\/nav.10011","volume":"49","author":"S. Alpern","year":"2002","unstructured":"Alpern, S.: Rendezvous search on labelled networks. Naval Research Logistics\u00a049, 256\u2013274 (2002)","journal-title":"Naval Research Logistics"},{"key":"31_CR4","unstructured":"Alpern, S., Gal, S.: The theory of search games and rendezvous. Int. Series in Operations research and Management Science. Kluwer Academic Publisher (2002)"},{"key":"31_CR5","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1239\/jap\/1032374243","volume":"36","author":"J. Alpern","year":"1999","unstructured":"Alpern, J., Baston, V., Essegaier, S.: Rendezvous search on a graph. Journal of Applied Probability\u00a036, 223\u2013231 (1999)","journal-title":"Journal of Applied Probability"},{"key":"31_CR6","doi-asserted-by":"crossref","unstructured":"Anderson, E., Fekete, S.: Asymmetric rendezvous on the plane. In: SoCG 1998, pp. 365\u2013373 (1998)","DOI":"10.1145\/276884.276925"},{"key":"31_CR7","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Slonim, D.K.: The power of team exploration: Two robots can learn unlabeled directed graphs. In: FOCS 1994, pp. 75\u201385 (1994)","DOI":"10.1109\/SFCS.1994.365703"},{"key":"31_CR8","doi-asserted-by":"crossref","unstructured":"Boldi, P., Vigna, S.: Computing Anonymously with Arbitrary Knowledge. In: PODC 1999, pp. 181\u2013188 (1999)","DOI":"10.1145\/301308.301355"},{"key":"31_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/3-540-45414-4_3","volume-title":"Distributed Computing","author":"P. Boldi","year":"2001","unstructured":"Boldi, P., Vigna, S.: An Effective Characterization of Computability in Anonymous Networks. In: Welch, J.L. (ed.) DISC 2001. LNCS, vol.\u00a02180, pp. 33\u201347. Springer, Heidelberg (2001)"},{"issue":"1-3","key":"31_CR10","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0012-365X(00)00455-6","volume":"243","author":"P. Boldi","year":"2002","unstructured":"Boldi, P., Vigna, S.: Fibrations of graphs. Disc. Maths\u00a0243(1-3), 21\u201366 (2002)","journal-title":"Disc. Maths"},{"key":"31_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/978-3-642-17653-1_10","volume-title":"Principles of Distributed Systems","author":"J. Chalopin","year":"2010","unstructured":"Chalopin, J., Das, S., Kosowski, A.: Constructing a Map of an Anonymous Graph: Applications of Universal Sequences. In: Lu, C., Masuzawa, T., Mosbah, M. (eds.) OPODIS 2010. LNCS, vol.\u00a06490, pp. 119\u2013134. Springer, Heidelberg (2010)"},{"key":"31_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/978-3-540-87779-0_4","volume-title":"Distributed Computing","author":"J. Chalopin","year":"2008","unstructured":"Chalopin, J., Godard, E., M\u00e9tivier, Y.: Local Terminations and Distributed Computability in Anonymous Networks. In: Taubenfeld, G. (ed.) DISC 2008. LNCS, vol.\u00a05218, pp. 47\u201362. Springer, Heidelberg (2008)"},{"key":"31_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1181","DOI":"10.1007\/3-540-45061-0_90","volume-title":"Automata, Languages and Programming","author":"M. Cieliebak","year":"2003","unstructured":"Cieliebak, M., Flocchini, P., Prencipe, G., Santoro, N.: Solving the Robots Gathering Problem. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 1181\u20131196. Springer, Heidelberg (2003)"},{"key":"31_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1007\/978-3-642-14162-1_42","volume-title":"Automata, Languages and Programming","author":"A. Collins","year":"2010","unstructured":"Collins, A., Czyzowicz, J., G\u0105sieniec, L., Labourel, A.: Tell Me Where I Am So I Can Meet You Sooner. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol.\u00a06199, pp. 502\u2013514. Springer, Heidelberg (2010)"},{"key":"31_CR15","doi-asserted-by":"crossref","unstructured":"Czyzowicz, J., Labourel, A., Pelc, A.: How to meet asynchronously (almost) everywhere. In: SODA 2010, pp. 22\u201330 (2010)","DOI":"10.1137\/1.9781611973075.3"},{"key":"31_CR16","doi-asserted-by":"crossref","unstructured":"Czyzowicz, J., Kosowski, A., Pelc, A.: How to meet when you forget: Log-space rendezvous in arbitrary graphs. In: PODC 2010, pp. 450\u2013459 (2010)","DOI":"10.1145\/1835698.1835801"},{"key":"31_CR17","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: PODC 2010, pp. 267\u2013276 (2010)","DOI":"10.1145\/1835698.1835761"},{"key":"31_CR18","doi-asserted-by":"crossref","unstructured":"Das Sarma, A., Holzer, S., Kor, L., Korman, A., Nanongkai, D., Pandurangan, G., Peleg, D., Wattenhofer, R.: Distributed Verification and Hardness of Distributed Approximation. In: STOC 2011, pp. 363\u2013372 (2011)","DOI":"10.1145\/1993636.1993686"},{"key":"31_CR19","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. Journal of Graph Theory\u00a032, 265\u2013297 (1999)","journal-title":"Journal of Graph Theory"},{"key":"31_CR20","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/s00453-006-0074-2","volume":"46","author":"A. Dessmark","year":"2006","unstructured":"Dessmark, A., Fraigniaud, P., Kowalski, D., Pelc, A.: Deterministic rendezvous in graphs. Algorithmica\u00a046, 69\u201396 (2006)","journal-title":"Algorithmica"},{"key":"31_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/3-540-44693-1_22","volume-title":"STACS 2001","author":"P. Flocchini","year":"2001","unstructured":"Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Gathering of Asynchronous Oblivious Robots with Limited Visibility. In: Ferreira, A., Reichel, H. (eds.) STACS 2001. LNCS, vol.\u00a02010, pp. 247\u2013258. Springer, Heidelberg (2001)"},{"key":"31_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1007\/978-3-540-24749-4_22","volume-title":"STACS 2004","author":"P. Fraigniaud","year":"2004","unstructured":"Fraigniaud, P., Ilcinkas, D.: Digraphs Exploration with Little Memory. In: Diekert, V., Habib, M. (eds.) STACS 2004. LNCS, vol.\u00a02996, pp. 246\u2013257. Springer, Heidelberg (2004)"},{"key":"31_CR23","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Korman, A., Peleg, D.: Local Distributed Decision. In: FOCS 2011, pp. 708\u2013717 (2011)","DOI":"10.1109\/FOCS.2011.17"},{"key":"31_CR24","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1002\/net.20127","volume":"48","author":"P. Fraigniaud","year":"2006","unstructured":"Fraigniaud, P., Gasieniec, L., Kowalski, D., Pelc, A.: Collective tree exploration. Networks\u00a048, 166\u2013177 (2006)","journal-title":"Networks"},{"key":"31_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1007\/978-3-540-87779-0_17","volume-title":"Distributed Computing","author":"P. Fraigniaud","year":"2008","unstructured":"Fraigniaud, P., Pelc, A.: Deterministic Rendezvous in Trees with Little Memory. In: Taubenfeld, G. (ed.) DISC 2008. LNCS, vol.\u00a05218, pp. 242\u2013256. Springer, Heidelberg (2008)"},{"key":"31_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/978-3-642-24100-0_34","volume-title":"Distributed Computing","author":"P. Fraigniaud","year":"2011","unstructured":"Fraigniaud, P., Rajsbaum, S., Travers, C.: Locality and Checkability in Wait-free Computing. In: Peleg, D. (ed.) DISC 2011. LNCS, vol.\u00a06950, pp. 333\u2013347. Springer, Heidelberg (2011)"},{"key":"31_CR27","unstructured":"Gasieniec, L., Pelc, A., Radzik, T., Zhang, X.: Tree exploration with logarithmic memory. In: SODA 2007, pp. 585\u2013594 (2007)"},{"key":"31_CR28","doi-asserted-by":"crossref","unstructured":"Goos, M., Suomela, J.: Locally checkable proofs. In: PODC 2011, pp. 159\u2013168 (2011)","DOI":"10.1145\/1993806.1993829"},{"key":"31_CR29","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/s00446-010-0095-3","volume":"22","author":"A. Korman","year":"2010","unstructured":"Korman, A., Kutten, S., Peleg, D.: Proof Labeling Schemes. Distributed Computing\u00a022, 215\u2013233 (2010)","journal-title":"Distributed Computing"},{"key":"31_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1007\/11780823_5","volume-title":"Structural Information and Communication Complexity","author":"D. Kowalski","year":"2006","unstructured":"Kowalski, D., Malinowski, A.: How to Meet in Anonymous Network. In: Flocchini, P., G\u0105sieniec, L. (eds.) SIROCCO 2006. LNCS, vol.\u00a04056, pp. 44\u201358. Springer, Heidelberg (2006)"},{"key":"31_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1007\/978-3-540-78773-0_52","volume-title":"LATIN 2008: Theoretical Informatics","author":"E. Kranakis","year":"2008","unstructured":"Kranakis, E., Krizanc, D., Morin, P.: Randomized Rendez-Vous with Limited Memory. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds.) LATIN 2008. LNCS, vol.\u00a04957, pp. 605\u2013616. Springer, Heidelberg (2008)"},{"key":"31_CR32","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/0166-218X(93)E0133-J","volume":"56","author":"N. Norris","year":"1995","unstructured":"Norris, N.: Universal covers of graphs: Isomorphism to depth n\u2009\u2212\u20091 implies isomorphism to all depths. Discrete Applied Mathematics\u00a056, 61\u201374 (1995)","journal-title":"Discrete Applied Mathematics"},{"issue":"6","key":"31_CR33","doi-asserted-by":"publisher","first-page":"1259","DOI":"10.1137\/S0097539793254571","volume":"24","author":"M. Naor","year":"1995","unstructured":"Naor, M., Stockmeyer, L.: What can be computed locally? SIAM J. Comput.\u00a024(6), 1259\u20131277 (1995)","journal-title":"SIAM J. Comput."},{"key":"31_CR34","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1391289.1391291","volume":"55","author":"O. Reingold","year":"2008","unstructured":"Reingold, O.: Undirected connectivity in log-space. JACM\u00a055, 1\u201324 (2008)","journal-title":"JACM"},{"key":"31_CR35","unstructured":"Ta-Shma, A., Zwick, U.: Deterministic rendezvous, treasure hunts and strongly universal exploration sequences. In: SODA 2007, pp. 599\u2013608 (2007)"},{"key":"31_CR36","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1109\/71.481599","volume":"7","author":"M. Yamashita","year":"1996","unstructured":"Yamashita, M., Kameda, T.: Computing on Anonymous Networks: Part I-Characterizing the Solvable Cases. IEEE Trans. Par. Distrib. Syst.\u00a07, 69\u201389 (1996)","journal-title":"IEEE Trans. Par. Distrib. Syst."},{"issue":"4","key":"31_CR37","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1007\/BF01192691","volume":"29","author":"M. Yamashita","year":"1996","unstructured":"Yamashita, M., Kameda, T.: Computing Functions on Asynchronous Anonymous Networks. Mathematical Systems Theory\u00a029(4), 331\u2013356 (1996)","journal-title":"Mathematical Systems Theory"},{"issue":"9","key":"31_CR38","doi-asserted-by":"publisher","first-page":"878","DOI":"10.1109\/71.798313","volume":"10","author":"M. Yamashita","year":"1999","unstructured":"Yamashita, M., Kameda, T.: Leader Election Problem on Networks in which Processor Identity Numbers Are Not Distinct. IEEE Trans. Parallel Distrib. Syst.\u00a010(9), 878\u2013887 (1999)","journal-title":"IEEE Trans. Parallel Distrib. Syst."}],"container-title":["Lecture Notes in Computer Science","LATIN 2012: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-29344-3_31.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T18:31:17Z","timestamp":1742927477000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-29344-3_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642293436","9783642293443"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-29344-3_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}