{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T17:01:33Z","timestamp":1780074093807,"version":"3.54.0"},"publisher-location":"New York, NY, USA","reference-count":32,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,1,4]],"date-time":"2018-01-04T00:00:00Z","timestamp":1515024000000},"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":[],"published-print":{"date-parts":[[2018,1,4]]},"DOI":"10.1145\/3154273.3154321","type":"proceedings-article","created":{"date-parts":[[2018,1,12]],"date-time":"2018-01-12T13:49:57Z","timestamp":1515764997000},"page":"1-10","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["A Foundational Framework for Certified Impossibility Results with Mobile Robots on Graphs"],"prefix":"10.1145","author":[{"given":"Thibaut","family":"Balabonski","sequence":"first","affiliation":[{"name":"LRI, Universit\u00e9 Paris-Sud, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robin","family":"Pelle","sequence":"additional","affiliation":[{"name":"LRI, Universit\u00e9 Paris-Sud, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lionel","family":"Rieg","sequence":"additional","affiliation":[{"name":"Yale University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S\u00e9bastien","family":"Tixeuil","sequence":"additional","affiliation":[{"name":"UPMC Sorbonne Universtit\u00e9s, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,1,4]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"crossref","unstructured":"C\u00e9dric Auger Zohir Bouzid Pierre Courtieu S\u00e9bastien Tixeuil and Xavier Urbain. 2013. Certified Impossibility Results for Byzantine-Tolerant Mobile Robots. In Stabilization Safety and Security of Distributed Systems - 15th International Symposium (SSS 2013) (Lecture Notes in Computer Science) Teruo Higashino Yoshiaki Katayama Toshimitsu Masuzawa Maria Potop-Butucaru and Masafumi Yamashita (Eds.) Vol. 8255. Springer-Verlag Osaka Japan 178--186.  C\u00e9dric Auger Zohir Bouzid Pierre Courtieu S\u00e9bastien Tixeuil and Xavier Urbain. 2013. Certified Impossibility Results for Byzantine-Tolerant Mobile Robots. In Stabilization Safety and Security of Distributed Systems - 15th International Symposium (SSS 2013) (Lecture Notes in Computer Science) Teruo Higashino Yoshiaki Katayama Toshimitsu Masuzawa Maria Potop-Butucaru and Masafumi Yamashita (Eds.) Vol. 8255. Springer-Verlag Osaka Japan 178--186.","DOI":"10.1007\/978-3-319-03089-0_13"},{"key":"e_1_3_2_1_2_1","volume-title":"Stabilization, Safety, and Security of Distributed Systems - 18th International Symposium, (SSS 2016) (Lecture Notes in Computer Science)","author":"Balabonski Thibaut","unstructured":"Thibaut Balabonski , Am\u00e9lie Delga , Lionel Rieg , S\u00e9bastien Tixeuil , and Xavier Urbain . 2016. Synchronous Gathering Without Multiplicity Detection: A Certified Algorithm . In Stabilization, Safety, and Security of Distributed Systems - 18th International Symposium, (SSS 2016) (Lecture Notes in Computer Science) , Borzoo Bonakdarpour and Frank Petit (Eds.), Vol. 10083 . Springer-Verlag , Lyon, France . Thibaut Balabonski, Am\u00e9lie Delga, Lionel Rieg, S\u00e9bastien Tixeuil, and Xavier Urbain. 2016. Synchronous Gathering Without Multiplicity Detection: A Certified Algorithm. In Stabilization, Safety, and Security of Distributed Systems - 18th International Symposium, (SSS 2016) (Lecture Notes in Computer Science), Borzoo Bonakdarpour and Frank Petit (Eds.), Vol. 10083. Springer-Verlag, Lyon, France."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.08.011"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-016-0271-1"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0124-0"},{"key":"e_1_3_2_1_6_1","volume-title":"24th International Symposium, DISC 2010, Cambridge, MA, USA, September 13-15, 2010. Proceedings (Lecture Notes in Computer Science), Nancy A. Lynch and Alexander A. Shvartsman (Eds.)","volume":"6343","author":"Blin L\u00e9lia","year":"2010","unstructured":"L\u00e9lia Blin , Alessia Milani , Maria Potop-Butucaru , and S\u00e9bastien Tixeuil . 2010 . Exclusive Perpetual Ring Exploration without Chirality. In Distributed Computing , 24th International Symposium, DISC 2010, Cambridge, MA, USA, September 13-15, 2010. Proceedings (Lecture Notes in Computer Science), Nancy A. Lynch and Alexander A. Shvartsman (Eds.) , Vol. 6343 . Springer, 312--327. L\u00e9lia Blin, Alessia Milani, Maria Potop-Butucaru, and S\u00e9bastien Tixeuil. 2010. Exclusive Perpetual Ring Exploration without Chirality. In Distributed Computing, 24th International Symposium, DISC 2010, Cambridge, MA, USA, September 13-15, 2010. Proceedings (Lecture Notes in Computer Science), Nancy A. Lynch and Alexander A. Shvartsman (Eds.), Vol. 6343. Springer, 312--327."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/SRDSW.2014.34"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25873-2_18"},{"key":"e_1_3_2_1_9_1","first-page":"101","article-title":"Formal Methods for Mobile Robots: Current Results and Open Problems","volume":"7","author":"B\u00e9rard B\u00e9atrice","year":"2015","unstructured":"B\u00e9atrice B\u00e9rard , Pierre Courtieu , Laure Millet , Maria Potop-Butucaru , Lionel Rieg , Nathalie Sznajder , S\u00e9bastien Tixeuil , and Xavier Urbain . 2015 . Formal Methods for Mobile Robots: Current Results and Open Problems . International Journal of Informatics Society 7 , 3 (2015), 101 -- 114 . http:\/\/www.infsoc.org\/journal\/vol07\/IJIS_07_3_101-114.pdf Invited Paper. B\u00e9atrice B\u00e9rard, Pierre Courtieu, Laure Millet, Maria Potop-Butucaru, Lionel Rieg, Nathalie Sznajder, S\u00e9bastien Tixeuil, and Xavier Urbain. 2015. Formal Methods for Mobile Robots: Current Results and Open Problems. International Journal of Informatics Society 7, 3 (2015), 101--114. http:\/\/www.infsoc.org\/journal\/vol07\/IJIS_07_3_101-114.pdf Invited Paper.","journal-title":"International Journal of Informatics Society"},{"key":"e_1_3_2_1_10_1","unstructured":"Pierre Cast\u00e9ran Vincent Filou and Mohamed Mosbah. 2009. Certifying Distributed Algorithms by Embedding Local Computation Systems in the Coq Proof Assistant. In Symbolic Computation in Software Science (SCSS'09) Adel Bouhoula and Tetsuo Ida (Eds.).  Pierre Cast\u00e9ran Vincent Filou and Mohamed Mosbah. 2009. Certifying Distributed Algorithms by Embedding Local Computation Systems in the Coq Proof Assistant. In Symbolic Computation in Software Science (SCSS'09) Adel Bouhoula and Tetsuo Ida (Eds.)."},{"key":"e_1_3_2_1_11_1","volume-title":"WG 2010, Zar\u00f3s","volume":"6410","author":"Chalopin J\u00e9r\u00e9mie","year":"2010","unstructured":"J\u00e9r\u00e9mie Chalopin , Paola Flocchini , Bernard Mans , and Nicola Santoro . 2010 . Network Exploration by Silent and Oblivious Robots. In Graph Theoretic Concepts in Computer Science - 36th International Workshop , WG 2010, Zar\u00f3s , Crete, Greece , June 28-30, 2010 Revised Papers (Lecture Notes in Computer Science), Dimitrios M. Thilikos (Ed.), Vol. 6410 . 208--219. J\u00e9r\u00e9mie Chalopin, Paola Flocchini, Bernard Mans, and Nicola Santoro. 2010. Network Exploration by Silent and Oblivious Robots. In Graph Theoretic Concepts in Computer Science - 36th International Workshop, WG 2010, Zar\u00f3s, Crete, Greece, June 28-30, 2010 Revised Papers (Lecture Notes in Computer Science), Dimitrios M. Thilikos (Ed.), Vol. 6410. 208--219."},{"key":"e_1_3_2_1_12_1","volume-title":"Ad-hoc, Mobile, and Wireless Networks - 15th International Conference, ADHOC-NOW","author":"Bonnet Fran\u00e7ois","year":"2015","unstructured":"Fran\u00e7ois Bonnet , Maria Potop-Butucaru , and S\u00e9bastien Tixeuil . 2016. Asynchrnous gathering in rings with four robots . In Ad-hoc, Mobile, and Wireless Networks - 15th International Conference, ADHOC-NOW 2015 , Lille, France , 2016, Proceedings (Lecture Notes in Computer Science). Springer . Fran\u00e7ois Bonnet, Maria Potop-Butucaru, and S\u00e9bastien Tixeuil. 2016. Asynchrnous gathering in rings with four robots. In Ad-hoc, Mobile, and Wireless Networks - 15th International Conference, ADHOC-NOW 2015, Lille, France, 2016, Proceedings (Lecture Notes in Computer Science). Springer."},{"key":"e_1_3_2_1_13_1","volume-title":"Inductively Defined Types. In International Conference on Computer Logic (Colog'88)","volume":"417","author":"Coquand Thierry","year":"1990","unstructured":"Thierry Coquand and Christine Paulin-Mohring . 1990 . Inductively Defined Types. In International Conference on Computer Logic (Colog'88) (Lecture Notes in Computer Science), Per Martin-L\u00f6f and Grigori Mints (Eds.) , Vol. 417 . Springer-Verlag, 50--66. Thierry Coquand and Christine Paulin-Mohring. 1990. Inductively Defined Types. In International Conference on Computer Logic (Colog'88) (Lecture Notes in Computer Science), Per Martin-L\u00f6f and Grigori Mints (Eds.), Vol. 417. Springer-Verlag, 50--66."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2014.11.001"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933070"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-016-0274-y"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9892-6"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33536-5_7"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-26850-7_13"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.05.031"},{"key":"e_1_3_2_1_21_1","volume-title":"Tokyo","volume":"10189","author":"Thu Doan Ha Thi","year":"2016","unstructured":"Ha Thi Thu Doan , Fran\u00e7ois Bonnet , and Kazuhiro Ogata . 2016 . Model Checking of a Mobile Robots Perpetual Exploration Algorithm. In Structured Object-Oriented Formal Language and Method - 6th International Workshop, SOFL+MSVL 2016 , Tokyo , Japan, November 15, 2016, Revised Selected Papers (Lecture Notes in Computer Science), Shaoying Liu, Zhenhua Duan, Cong Tian, and Fumiko Nagoya (Eds.) , Vol. 10189 . 201--219. Ha Thi Thu Doan, Fran\u00e7ois Bonnet, and Kazuhiro Ogata. 2016. Model Checking of a Mobile Robots Perpetual Exploration Algorithm. In Structured Object-Oriented Formal Language and Method - 6th International Workshop, SOFL+MSVL 2016, Tokyo, Japan, November 15, 2016, Revised Selected Papers (Lecture Notes in Computer Science), Shaoying Liu, Zhenhua Duan, Cong Tian, and Fumiko Nagoya (Eds.), Vol. 10189. 201--219."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.01.007"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9611-5"},{"key":"e_1_3_2_1_24_1","volume-title":"Distributed Computing by Oblivious Mobile Robots","author":"Flocchini Paola","unstructured":"Paola Flocchini , Giuseppe Prencipe , and Nicola Santoro . 2012. Distributed Computing by Oblivious Mobile Robots . Morgan & Claypool Publishers . Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. 2012. Distributed Computing by Oblivious Mobile Robots. Morgan & Claypool Publishers."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13284-1_9"},{"key":"e_1_3_2_1_26_1","volume-title":"18th International Colloquium, SIROCCO 2011, Gdansk, Poland, June 26-29, 2011. Proceedings (Lecture Notes in Computer Science), Adrian Kosowski and Masafumi Yamashita (Eds.)","volume":"6796","author":"Kamei Sayaka","year":"2011","unstructured":"Sayaka Kamei , Anissa Lamani , Fukuhito Ooshita , and S\u00e9bastien Tixeuil . 2011 . Asynchronous Mobile Robot Gathering from Symmetric Configurations without Global Multiplicity Detection. In Structural Information and Communication Complexity - 18th International Colloquium, SIROCCO 2011, Gdansk, Poland, June 26-29, 2011. Proceedings (Lecture Notes in Computer Science), Adrian Kosowski and Masafumi Yamashita (Eds.) , Vol. 6796 . Springer, 150--161. Sayaka Kamei, Anissa Lamani, Fukuhito Ooshita, and S\u00e9bastien Tixeuil. 2011. Asynchronous Mobile Robot Gathering from Symmetric Configurations without Global Multiplicity Detection. In Structural Information and Communication Complexity - 18th International Colloquium, SIROCCO 2011, Gdansk, Poland, June 26-29, 2011. Proceedings (Lecture Notes in Computer Science), Adrian Kosowski and Masafumi Yamashita (Eds.), Vol. 6796. Springer, 150--161."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32589-2_48"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13284-1_15"},{"key":"e_1_3_2_1_29_1","volume-title":"Stabilization, Safety, and Security of Distributed Systems - 16th International Symposium, (SSS 2014) (Lecture Notes in Computer Science), Pascal Felber and Vijay K","author":"Millet Laure","unstructured":"Laure Millet , Maria Potop-Butucaru , Nathalie Sznajder , and S\u00e9bastien Tixeuil . 2014. On the Synthesis of Mobile Robots Algorithms: The Case of Ring Gathering . In Stabilization, Safety, and Security of Distributed Systems - 16th International Symposium, (SSS 2014) (Lecture Notes in Computer Science), Pascal Felber and Vijay K . Garg (Eds.), Vol. 8756 . Springer-Verlag , Paderborn, Germany , 237--251. Laure Millet, Maria Potop-Butucaru, Nathalie Sznajder, and S\u00e9bastien Tixeuil. 2014. On the Synthesis of Mobile Robots Algorithms: The Case of Ring Gathering. In Stabilization, Safety, and Security of Distributed Systems - 16th International Symposium, (SSS 2014) (Lecture Notes in Computer Science), Pascal Felber and Vijay K. Garg (Eds.), Vol. 8756. Springer-Verlag, Paderborn, Germany, 237--251."},{"key":"e_1_3_2_1_30_1","volume-title":"PRIMA 2015: Principles and Practice of Multi-Agent Systems - 18th International Conference","author":"Rubin Sasha","year":"2015","unstructured":"Sasha Rubin , Florian Zuleger , Aniello Murano , and Benjamin Aminof . 2015. Verification of Asynchronous Mobile-Robots in Partially-Known Environments . In PRIMA 2015: Principles and Practice of Multi-Agent Systems - 18th International Conference , Bertinoro, Italy, October 26-30, 2015 , Proceedings (Lecture Notes in Computer Science), Qingliang Chen, Paolo Torroni, Serena Villata, Jane Yungjen Hsu, and Andrea Omicini (Eds.), Vol. 9387 . Springer-Verlag , 185--200. Sasha Rubin, Florian Zuleger, Aniello Murano, and Benjamin Aminof. 2015. Verification of Asynchronous Mobile-Robots in Partially-Known Environments. In PRIMA 2015: Principles and Practice of Multi-Agent Systems - 18th International Conference, Bertinoro, Italy, October 26-30, 2015, Proceedings (Lecture Notes in Computer Science), Qingliang Chen, Paolo Torroni, Serena Villata, Jane Yungjen Hsu, and Andrea Omicini (Eds.), Vol. 9387. Springer-Verlag, 185--200."},{"key":"e_1_3_2_1_31_1","volume-title":"Formal Methods in Computer Aided Design.","author":"Sangnier Arnaud","unstructured":"Arnaud Sangnier , Nathalie Sznajder , Maria Potop-Butucaru , and S\u00e9bastien Tixeuil . 2017. Parameterized Verification of Algorithms for Oblivious Robots on a Ring . In Formal Methods in Computer Aided Design. Vienna, Austria . http:\/\/arxiv.org\/abs\/1706.05193 Arnaud Sangnier, Nathalie Sznajder, Maria Potop-Butucaru, and S\u00e9bastien Tixeuil. 2017. Parameterized Verification of Algorithms for Oblivious Robots on a Ring. In Formal Methods in Computer Aided Design. Vienna, Austria. http:\/\/arxiv.org\/abs\/1706.05193"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979628292X"}],"event":{"name":"ICDCN '18: 19th International Conference on Distributed Computing and Networking","location":"Varanasi India","acronym":"ICDCN '18","sponsor":["SIGMOBILE ACM Special Interest Group on Mobility of Systems, Users, Data and Computing","SIGOPS ACM Special Interest Group on Operating Systems"]},"container-title":["Proceedings of the 19th International Conference on Distributed Computing and Networking"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3154273.3154321","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3154273.3154321","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:11:26Z","timestamp":1750212686000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3154273.3154321"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1,4]]},"references-count":32,"alternative-id":["10.1145\/3154273.3154321","10.1145\/3154273"],"URL":"https:\/\/doi.org\/10.1145\/3154273.3154321","relation":{},"subject":[],"published":{"date-parts":[[2018,1,4]]},"assertion":[{"value":"2018-01-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}