{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:33:41Z","timestamp":1759638821271,"version":"3.40.3"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030795269"},{"type":"electronic","value":"9783030795276"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-79527-6_3","type":"book-chapter","created":{"date-parts":[[2021,6,19]],"date-time":"2021-06-19T11:03:43Z","timestamp":1624100623000},"page":"31-49","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Distributed Graph Problems Through an\u00a0Automata-Theoretic Lens"],"prefix":"10.1007","author":[{"given":"Yi-Jun","family":"Chang","sequence":"first","affiliation":[]},{"given":"Jan","family":"Studen\u00fd","sequence":"additional","affiliation":[]},{"given":"Jukka","family":"Suomela","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,6,20]]},"reference":[{"key":"3_CR1","doi-asserted-by":"publisher","unstructured":"Balliu, A., Brandt, S., Chang, Y.J., Olivetti, D., Rabie, M., Suomela, J.: The distributed complexity of locally checkable problems on paths is decidable. In: PODC 2019 (2019). https:\/\/doi.org\/10.1145\/3293611.3331606","DOI":"10.1145\/3293611.3331606"},{"key":"3_CR2","doi-asserted-by":"crossref","unstructured":"Balliu, A., et al.: Classification of distributed binary labeling problems. In: DISC 2020 (2020)","DOI":"10.1145\/3382734.3405703"},{"key":"3_CR3","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1109\/FOCS.2019.00037","volume":"2019","author":"A Balliu","year":"2019","unstructured":"Balliu, A., Brandt, S., Hirvonen, J., Olivetti, D., Rabie, M., Suomela, J.: Lower bounds for maximal matchings and maximal independent sets. FOCS 2019, 481\u2013497 (2019). https:\/\/doi.org\/10.1109\/FOCS.2019.00037","journal-title":"FOCS"},{"key":"3_CR4","doi-asserted-by":"publisher","unstructured":"Balliu, A., Brandt, S., Olivetti, D., Suomela, J.: Almost global problems in the LOCAL model. In: DISC 2018 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2018.9","DOI":"10.4230\/LIPIcs.DISC.2018.9"},{"key":"3_CR5","doi-asserted-by":"publisher","unstructured":"Balliu, A., Brandt, S., Olivetti, D., Suomela, J.: How much does randomness help with locally checkable problems? In: PODC 2020 (2020). https:\/\/doi.org\/10.1145\/3382734.3405715","DOI":"10.1145\/3382734.3405715"},{"key":"3_CR6","doi-asserted-by":"publisher","unstructured":"Balliu, A., Hirvonen, J., Korhonen, J.H., Lempi\u00e4inen, T., Olivetti, D., Suomela, J.: New classes of distributed time complexity. In: STOC 2018 (2018). https:\/\/doi.org\/10.1145\/3188745.3188860","DOI":"10.1145\/3188745.3188860"},{"key":"3_CR7","doi-asserted-by":"crossref","unstructured":"Barenboim, L., Elkin, M., Pettie, S., Schneider, J.: The locality of distributed symmetry breaking. J. ACM 63(3), 20 (2016)","DOI":"10.1145\/2903137"},{"key":"3_CR8","doi-asserted-by":"publisher","unstructured":"Brandt, S., et al.: A lower bound for the distributed Lov\u00e1sz local lemma. In: STOC 2016 (2016). https:\/\/doi.org\/10.1145\/2897518.2897570","DOI":"10.1145\/2897518.2897570"},{"key":"3_CR9","doi-asserted-by":"publisher","unstructured":"Brandt, S., et al.: LCL problems on grids. In: PODC 2017, (2017). https:\/\/doi.org\/10.1145\/3087801.3087833","DOI":"10.1145\/3087801.3087833"},{"key":"3_CR10","unstructured":"\u010cern\u00fd, J.: Pozn\u00e1mka k homog\u00e9nnym experimentom s kone\u010dn\u00fdmi automatmi. Matematicko-fyzik\u00e1lny \u010dasopis 14(3), 208\u2013216 (1964), http:\/\/dml.cz\/dmlcz\/126647"},{"key":"3_CR11","doi-asserted-by":"publisher","unstructured":"Chang, Y.J.: The complexity landscape of distributed locally checkable problems on trees. In: DISC 2020 (2020). https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2020.18","DOI":"10.4230\/LIPIcs.DISC.2020.18"},{"issue":"1","key":"3_CR12","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1137\/17M1117537","volume":"48","author":"YJ Chang","year":"2019","unstructured":"Chang, Y.J., Kopelowitz, T., Pettie, S.: An exponential separation between randomized and deterministic complexity in the local model. SIAM J. Comput. 48(1), 122\u2013143 (2019). https:\/\/doi.org\/10.1137\/17M1117537","journal-title":"SIAM J. Comput."},{"issue":"1","key":"3_CR13","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1137\/17M1157957","volume":"48","author":"YJ Chang","year":"2019","unstructured":"Chang, Y.J., Pettie, S.: A time hierarchy theorem for the LOCAL model. SIAM J. Comput. 48(1), 33\u201369 (2019). https:\/\/doi.org\/10.1137\/17M1157957","journal-title":"SIAM J. Comput."},{"key":"3_CR14","unstructured":"Chang, Y.J., Studen\u00fd, J., Suomela, J.: Distributed graph problems through an automata-theoretic lens (2020), https:\/\/arxiv.org\/abs\/2002.07659"},{"issue":"1","key":"3_CR15","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/S0019-9958(86)80023-7","volume":"70","author":"R Cole","year":"1986","unstructured":"Cole, R., Vishkin, U.: Deterministic coin tossing with applications to optimal parallel list ranking. Inf. Control 70(1), 32\u201353 (1986). https:\/\/doi.org\/10.1016\/S0019-9958(86)80023-7","journal-title":"Inf. Control"},{"issue":"4","key":"3_CR16","first-page":"307","volume":"23","author":"H Don","year":"2018","unstructured":"Don, H., Zantema, H.: Synchronizing non-deterministic finite automata. J. Automat. Lang. Comb. 23(4), 307\u2013328 (2018)","journal-title":"J. Automat. Lang. Comb."},{"issue":"3","key":"3_CR17","doi-asserted-by":"publisher","first-page":"500","DOI":"10.1137\/0219033","volume":"19","author":"D Eppstein","year":"1990","unstructured":"Eppstein, D.: Reset sequences for monotonic automata. SIAM J. Comput. 19(3), 500\u2013510 (1990). https:\/\/doi.org\/10.1137\/0219033","journal-title":"SIAM J. Comput."},{"key":"3_CR18","doi-asserted-by":"publisher","unstructured":"Fich, F.E., Ramachandran, V.: Lower bounds for parallel computation on linked structures. In: SPAA 1990 (1990). https:\/\/doi.org\/10.1145\/97444.97676","DOI":"10.1145\/97444.97676"},{"key":"3_CR19","doi-asserted-by":"publisher","unstructured":"Fischer, M., Ghaffari, M.: Sublogarithmic distributed algorithms for Lov\u00e1sz local lemma, and the complexity hierarchy. In: DISC 2017 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2017.18","DOI":"10.4230\/LIPIcs.DISC.2017.18"},{"issue":"17","key":"3_CR20","doi-asserted-by":"publisher","first-page":"986","DOI":"10.1016\/j.ipl.2009.05.007","volume":"109","author":"Z Gazdag","year":"2009","unstructured":"Gazdag, Z., Iv\u00e1n, S., Nagy-Gy\u00f6rgy, J.: Improved upper bounds on synchronizing nondeterministic automata. Inf. Proces. Lett. 109(17), 986\u2013990 (2009). https:\/\/doi.org\/10.1016\/j.ipl.2009.05.007","journal-title":"Inf. Proces. Lett."},{"key":"3_CR21","doi-asserted-by":"publisher","unstructured":"Ghaffari, M., Harris, D.G., Kuhn, F.: On derandomizing local distributed algorithms. In: FOCS 2018 (2018). https:\/\/doi.org\/10.1109\/FOCS.2018.00069","DOI":"10.1109\/FOCS.2018.00069"},{"key":"3_CR22","doi-asserted-by":"publisher","unstructured":"Ghaffari, M., Su, H.H.: Distributed degree splitting, edge coloring, and orientations. In: SODA 2017 (2017). https:\/\/doi.org\/10.1137\/1.9781611974782.166","DOI":"10.1137\/1.9781611974782.166"},{"issue":"1","key":"3_CR23","first-page":"1","volume":"17","author":"B Imreh","year":"2005","unstructured":"Imreh, B., Ito, M.: On regular languages determined by nondeterministic directable automata. Acta Cybernet. 17(1), 1\u201310 (2005)","journal-title":"Acta Cybernet."},{"issue":"1","key":"3_CR24","first-page":"105","volume":"14","author":"B Imreh","year":"1999","unstructured":"Imreh, B., Steinby, M.: Directable nondeterministic automata. Acta Cybernetica 14(1), 105\u2013115 (1999)","journal-title":"Acta Cybernetica"},{"issue":"1","key":"3_CR25","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"N Linial","year":"1992","unstructured":"Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193\u2013201 (1992). https:\/\/doi.org\/10.1137\/0221015","journal-title":"SIAM J. Comput."},{"issue":"2","key":"3_CR26","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s00224-013-9516-6","volume":"54","author":"P Martyugin","year":"2013","unstructured":"Martyugin, P.: Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata. Theor. Comput. Syst. 54(2), 293\u2013304 (2013). https:\/\/doi.org\/10.1007\/s00224-013-9516-6","journal-title":"Theor. Comput. Syst."},{"issue":"6","key":"3_CR27","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. 24(6), 1259\u20131277 (1995). https:\/\/doi.org\/10.1137\/S0097539793254571","journal-title":"SIAM J. Comput."},{"key":"3_CR28","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772","author":"D Peleg","year":"2000","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM (2000). https:\/\/doi.org\/10.1137\/1.9780898719772","journal-title":"Distributed Computing: A Locality-Sensitive Approach. SIAM"},{"key":"3_CR29","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/j.ic.2014.12.018","volume":"243","author":"S Pettie","year":"2015","unstructured":"Pettie, S., Su, H.H.: Distributed algorithms for coloring triangle-free graphs. Inf. Comput. 243, 263\u2013280 (2015)","journal-title":"Inf. Comput."},{"key":"3_CR30","doi-asserted-by":"publisher","unstructured":"Rozho\u0148, V., Ghaffari, M.: Polylogarithmic-time deterministic networkdecomposition and distributed derandomization. In: STOC 2020 (2020). https:\/\/doi.org\/10.1145\/3357713.3384298","DOI":"10.1145\/3357713.3384298"},{"key":"3_CR31","doi-asserted-by":"publisher","unstructured":"Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time. In: STOC 1973 (1973). https:\/\/doi.org\/10.1145\/800125.804029","DOI":"10.1145\/800125.804029"}],"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-030-79527-6_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,19]],"date-time":"2021-06-19T11:04:02Z","timestamp":1624100642000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-79527-6_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030795269","9783030795276"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-79527-6_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"20 June 2021","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":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28 June 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 July 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sirocco2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sirocco2021.ii.uni.wroc.pl\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"48","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"20","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"42% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"6","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}