{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:35:31Z","timestamp":1759638931142,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":25,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,7,16]],"date-time":"2019-07-16T00:00:00Z","timestamp":1563235200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"publisher","award":["Grant 285721"],"award-info":[{"award-number":["Grant 285721"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,7,16]]},"DOI":"10.1145\/3293611.3331606","type":"proceedings-article","created":{"date-parts":[[2019,7,19]],"date-time":"2019-07-19T13:17:21Z","timestamp":1563542241000},"page":"262-271","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["The Distributed Complexity of Locally Checkable Problems on Paths is Decidable"],"prefix":"10.1145","author":[{"given":"Alkida","family":"Balliu","sequence":"first","affiliation":[{"name":"Aalto University, Helsinki, Finland"}]},{"given":"Sebastian","family":"Brandt","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}]},{"given":"Yi-Jun","family":"Chang","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, MI, USA"}]},{"given":"Dennis","family":"Olivetti","sequence":"additional","affiliation":[{"name":"Aalto University, Helsinki, Finland"}]},{"given":"Mika\u00ebl","family":"Rabie","sequence":"additional","affiliation":[{"name":"Aalto University & IRIF, University of Paris, Paris, France"}]},{"given":"Jukka","family":"Suomela","sequence":"additional","affiliation":[{"name":"Aalto University, Helsinki, Finland"}]}],"member":"320","published-online":{"date-parts":[[2019,7,16]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"The distributed complexity of locally checkable problems on paths is decidable. arXiv preprint arXiv:1811.01672","author":"Balliu Alkida","year":"2018","unstructured":"Alkida Balliu , Sebastian Brandt , Yi-Jun Chang , Dennis Olivetti , Mika\u00ebl Rabie , and Jukka Suomela . 2018a. The distributed complexity of locally checkable problems on paths is decidable. arXiv preprint arXiv:1811.01672 ( 2018 ). Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Mika\u00ebl Rabie, and Jukka Suomela. 2018a. The distributed complexity of locally checkable problems on paths is decidable. arXiv preprint arXiv:1811.01672 (2018)."},{"key":"e_1_3_2_1_2_1","volume-title":"Proc. 32nd International Symposium on Distributed Computing (DISC 2018) (Leibniz International Proceedings in Informatics (LIPIcs)). Schloss Dagstuhl--Leibniz-Zentrum f\u00fc r Informatik.","author":"Balliu Alkida","year":"2018","unstructured":"Alkida Balliu , Sebastian Brandt , Dennis Olivetti , and Jukka Suomela . 2018 b. Almost global problems in the LOCAL model . In Proc. 32nd International Symposium on Distributed Computing (DISC 2018) (Leibniz International Proceedings in Informatics (LIPIcs)). Schloss Dagstuhl--Leibniz-Zentrum f\u00fc r Informatik. Alkida Balliu, Sebastian Brandt, Dennis Olivetti, and Jukka Suomela. 2018b. Almost global problems in the LOCAL model. In Proc. 32nd International Symposium on Distributed Computing (DISC 2018) (Leibniz International Proceedings in Informatics (LIPIcs)). Schloss Dagstuhl--Leibniz-Zentrum f\u00fc r Informatik."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188860"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-41528-4_9"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897570"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087833"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.72"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.23"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80023-7"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2015.09.002"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767133"},{"key":"e_1_3_2_1_12_1","volume-title":"Proc. 31st International Symposium on Distributed Computing (DISC","author":"Fischer Manuela","year":"2017","unstructured":"Manuela Fischer and Mohsen Ghaffari . 2017 . Sublogarithmic Distributed Algorithms for Lov\u00e1sz Local Lemma, and the Complexity Hierarchy . In Proc. 31st International Symposium on Distributed Computing (DISC 2017). 18:1--18:16. Manuela Fischer and Mohsen Ghaffari. 2017. Sublogarithmic Distributed Algorithms for Lov\u00e1sz Local Lemma, and the Complexity Hierarchy. In Proc. 31st International Symposium on Distributed Computing (DISC 2017). 18:1--18:16."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00069"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212764"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039852"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0401044"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.37236\/6862"},{"volume-title":"Introduction to Automata Theory, Languages and Computation","author":"Hopcroft John E","key":"e_1_3_2_1_18_1","unstructured":"John E Hopcroft and Jeffrey D Ullman . 1979. Introduction to Automata Theory, Languages and Computation . Addison-Wesley . John E Hopcroft and Jeffrey D Ullman. 1979. Introduction to Automata Theory, Languages and Computation. Addison-Wesley."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404036"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793254571"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200759"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_3_2_1_25_1","volume-title":"Automatically Speeding Up LOCAL Graph Algorithms. In 7th Workshop on Advances in Distributed Graph Algorithms (ADGA 2018","author":"Pettie Seth","year":"2018","unstructured":"Seth Pettie . 2018 . Automatically Speeding Up LOCAL Graph Algorithms. In 7th Workshop on Advances in Distributed Graph Algorithms (ADGA 2018 ). http:\/\/adga.hiit.fi\/2018\/Seth.pdf Seth Pettie. 2018. Automatically Speeding Up LOCAL Graph Algorithms. In 7th Workshop on Advances in Distributed Graph Algorithms (ADGA 2018). http:\/\/adga.hiit.fi\/2018\/Seth.pdf"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-25258-2_4"}],"event":{"name":"PODC '19: ACM Symposium on Principles of Distributed Computing","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Toronto ON Canada","acronym":"PODC '19"},"container-title":["Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3293611.3331606","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3293611.3331606","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:02:02Z","timestamp":1750208522000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3293611.3331606"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,16]]},"references-count":25,"alternative-id":["10.1145\/3293611.3331606","10.1145\/3293611"],"URL":"https:\/\/doi.org\/10.1145\/3293611.3331606","relation":{},"subject":[],"published":{"date-parts":[[2019,7,16]]},"assertion":[{"value":"2019-07-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}