Distributed graph problems through an automata-theoretic lens
References
[1]
Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Mikaël Rabie, Jukka Suomela, The distributed complexity of locally checkable problems on paths is decidable, in: Proc. 38th ACM Symposium on Principles of Distributed Computing (PODC 2019), ACM Press, 2019, pp. 262–271,.
[2]
Alkida Balliu, Sebastian Brandt, Yi-Jun Chang, Dennis Olivetti, Jan Studenỳ, Jukka Suomela, Efficient classification of locally checkable problems in regular trees, in: Proc. 36th International Symposium on Distributed Computing (DISC 2022), Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2022, pp. 22:1–22:19,.
[3]
Alkida Balliu, Sebastian Brandt, Yuval Efron, Juho Hirvonen, Yannic Maus, Dennis Olivetti, Jukka Suomela, Classification of distributed binary labeling problems, in: Proc. 34th International Symposium on Distributed Computing (DISC 2020), 2020,.
[4]
Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, Jukka Suomela, Lower bounds for maximal matchings and maximal independent sets, in: Proc. 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2019), IEEE, 2019, pp. 481–497,.
[5]
Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jan Studený, Jukka Suomela, Aleksandr Tereshchenko, Locally checkable problems in rooted trees, in: Proc. 40th ACM Symposium on Principles of Distributed Computing (PODC 2021), ACM Press, 2021, pp. 263–272,.
[6]
Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jukka Suomela, 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ür Informatik, 2018, pp. 9:1–9:16,.
[7]
Alkida Balliu, Sebastian Brandt, Dennis Olivetti, Jukka Suomela, How much does randomness help with locally checkable problems?, in: Proc. 39th Symposium on Principles of Distributed Computing (PODC 2020), New York, NY, USA, Association for Computing Machinery, 2020, pp. 299–308,.
[8]
Alkida Balliu, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Dennis Olivetti, Jukka Suomela, New classes of distributed time complexity, in: Proc. 50th ACM Symposium on Theory of Computing (STOC 2018), ACM Press, 2018, pp. 1307–1318,.
[9]
Leonid Barenboim, Michael Elkin, Seth Pettie, Johannes Schneider, The locality of distributed symmetry breaking, Journal of ACM 63 (3) (2016).
[10]
Sebastian Brandt, Yi-Jun Chang, Jan Grebík, Christoph Grunau, Václav Rozhoň, Zoltán Vidnyánszky, Local problems on trees from the perspectives of distributed algorithms, finitary factors, and descriptive combinatorics, in: LIPIcs, in: Proc. 13th Innovations in Theoretical Computer Science Conference, (ITCS 2022), vol. 215, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, pp. 29:1–29:26,.
[11]
Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempiäinen, Joel Rybicki, Jukka Suomela, Jara Uitto, A lower bound for the distributed Lovász local lemma, in: Proc. 48th ACM Symposium on Theory of Computing (STOC 2016), ACM Press, 2016, pp. 479–488,.
[12]
Sebastian Brandt, Juho Hirvonen, Janne H. Korhonen, Tuomo Lempiäinen, Patric R.J. Östergård, Christopher Purcell, Joel Rybicki, Jukka Suomela, Przemysław Uznański, LCL problems on grids, in: Proc. 36th ACM Symposium on Principles of Distributed Computing (PODC 2017), ACM Press, 2017, pp. 101–110,.
[13]
Ján Černý, Poznámka k homogénnym experimentom s konečnými automatmi, Matematicko-fyzikálny časopis 14 (3) (1964) 208–216. http://dml.cz/dmlcz/126647.
[14]
Yi-Jun Chang, The complexity landscape of distributed locally checkable problems on trees, in: Proc. 34th International Symposium on Distributed Computing (DISC 2020), vol. 179, 2020, pp. 18:1–18:17,.
[15]
Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie, An exponential separation between randomized and deterministic complexity in the local model, SIAM Journal on Computing 48 (1) (2019) 122–143,.
[16]
Yi-Jun Chang, Seth Pettie, A time hierarchy theorem for the LOCAL model, SIAM Journal on Computing 48 (1) (2019) 33–69,.
[17]
Yi-Jun Chang, Jan Studenỳ, Jukka Suomela, Distributed graph problems through an automata-theoretic lens, in: Proc. 28th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2021), Springer, 2021, pp. 31–49.
[18]
Marek Chrobak, Finite automata and unary languages, Theoretical Computer Science 47 (1986) 149–158,.
[19]
Richard Cole, Uzi Vishkin, Deterministic coin tossing with applications to optimal parallel list ranking, Information and Control 70 (1) (1986) 32–53,.
[20]
Henk Don, Hans Zantema, Synchronizing non-deterministic finite automata, Journal of Automata, Languages and Combinatorics 23 (4) (2018) 307–328.
[21]
David Eppstein, Reset sequences for monotonic automata, SIAM Journal on Computing 19 (3) (1990) 500–510,.
[22]
Faith E. Fich, Vijaya Ramachandran, Lower bounds for parallel computation on linked structures, in: Proc. 2nd Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA 1990), New York, NY, USA, ACM Press, 1990, pp. 109–116,.
[23]
Manuela Fischer, Mohsen Ghaffari, Sublogarithmic distributed algorithms for Lovász local lemma, and the complexity hierarchy, in: Proc. 31st International Symposium on Distributed Computing (DISC 2017), 2017, pp. 18:1–18:16,.
[24]
Zsolt Gazdag, Szabolcs Iván, Judit Nagy-György, Improved upper bounds on synchronizing nondeterministic automata, Information Processing Letters 109 (17) (2009) 986–990,.
[25]
Mohsen Ghaffari, David G. Harris, Fabian Kuhn, On derandomizing local distributed algorithms, in: Proc. 59th IEEE Symposium on Foundations of Computer Science (FOCS 2018), 2018, pp. 662–673,.
[26]
Mohsen Ghaffari, Hsin-Hao Su, Distributed degree splitting, edge coloring, and orientations, in: Proc. 28th ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Society for Industrial and Applied Mathematics, 2017, pp. 2505–2523,.
[27]
Andrew V. Goldberg, Serge A. Plotkin, Gregory E. Shannon, Parallel symmetry-breaking in sparse graphs, SIAM J. Discrete Math. 1 (4) (1988) 434.
[28]
Markus Holzer, Martin Kutrib, Descriptional and computational complexity of finite automata—a survey, Inf. Comput. 209 (3) (2011) 456–470,.
[29]
Balázs Imreh, Masami Ito, On regular languages determined by nondeterministic directable automata, Acta Cybern. 17 (1) (2005) 1–10.
[30]
Balázs Imreh, Magnus Steinby, Directable nondeterministic automata, Acta Cybern. 14 (1) (1999) 105–115.
[31]
Nathan Linial, Locality in distributed graph algorithms, SIAM J. Comput. 21 (1) (1992) 193–201,.
[32]
Pavel Martyugin, Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata, Theory Comput. Syst. 54 (2) (2014) 293–304,.
[33]
Moni Naor, Larry Stockmeyer, What can be computed locally?, SIAM J. Comput. 24 (6) (1995) 1259–1277,.
[34]
David Peleg, Distributed Computing: A Locality-Sensitive Approach, Society for Industrial and Applied Mathematics, 2000,.
[35]
Seth Pettie, Hsin-Hao Su, Distributed algorithms for coloring triangle-free graphs, Inf. Comput. 243 (2015) 263–280.
[36]
J.L. Ramírez-Alfonsín, Complexity of the Frobenius problem, Combinatorica 16 (1) (1996) 143–147,.
[37]
Václav Rozhoň, Mohsen Ghaffari, Polylogarithmic-time deterministic network decomposition and distributed derandomization, in: Proc. 52nd Annual ACM Symposium on Theory of Computing (STOC 2020), 2020,.
[38]
Jeffrey Shallit, The Frobenius problem and its generalizations, in: Proc. 12th International Conference on Developments in Language Theory (DLT 2008), in: LNCS, vol. 5257, Springer, Berlin, Heidelberg, 2008, pp. 72–83,.
[39]
L.J. Stockmeyer, A.R. Meyer, Word problems requiring exponential time, in: Proc. 5th Annual ACM Symposium on Theory of Computing (STOC 1973), New York, ACM Press, New York, USA, 1973, pp. 1–9,.
[40]
Anthony Widjaja To, Unary finite automata vs. arithmetic progressions, Inf. Process. Lett. 109 (17) (2009) 1010–1014,.
Recommendations
Distributed Graph Problems Through an Automata-Theoretic Lens
Structural Information and Communication ComplexityAbstractThe locality of a graph problem is the smallest distance T such that each node can choose its own part of the solution based on its radius-T neighborhood. In many settings, a graph problem can be solved efficiently with a distributed or parallel ...
Quantum versus deterministic counter automata
This paper focuses on quantum analogues of various models of counter automata, and almost completely proves the relation between the classes of languages recognizable by bounded error quantum ones and classical deterministic ones in every model of ...
Characterizations of 1-Way Quantum Finite Automata
The 2-way quantum finite automaton introduced by Kondacs and Watrous [ Proceedings of the 38 th Annual Symposium on Foundations of Computer Science , 1997, IEEE Computer Society, pp. 66--75] can accept nonregular languages with bounded error in ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
The Author(s).
Publisher
Elsevier Science Publishers Ltd.
United Kingdom
Publication History
Published: 24 March 2023
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 02 Oct 2024
Other Metrics
Citations
View Options
View options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in