Distributed graph problems through an automata-theoretic lens
DOI10.1016/J.TCS.2023.113710OpenAlexW4318069462MaRDI QIDQ2689441FDOQ2689441
Authors: Yi-Jun Chang, Jan Studený, Jukka Suomela 
Publication date: 10 March 2023
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2023.113710
Recommendations
computational complexitydistributed algorithmsautomata theoryalgorithm synthesisLOCAL modelLCL problems
Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)
Cites Work
- Distributed Computing: A Locality-Sensitive Approach
- Title not available (Why is that?)
- Locality in Distributed Graph Algorithms
- Complexity of the Frobenius problem
- Reset Sequences for Monotonic Automata
- Title not available (Why is that?)
- Descriptional and computational complexity of finite automata -- a survey
- Finite automata and unary languages
- Distributed coloring algorithms for triangle-free graphs
- The locality of distributed symmetry breaking
- Parallel Symmetry-Breaking in Sparse Graphs
- Unary finite automata vs. arithmetic progressions
- Deterministic coin tossing with applications to optimal parallel list ranking
- What Can be Computed Locally?
- Title not available (Why is that?)
- Lower Bounds for Maximal Matchings and Maximal Independent Sets
- Polylogarithmic-time deterministic network decomposition and distributed derandomization
- The Frobenius Problem and Its Generalizations
- A time hierarchy theorem for the LOCAL model
- Directable nondeterministic automata
- Improved upper bounds on synchronizing nondeterministic automata
- Synchronizing non-deterministic finite automata
- Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
- Distributed graph problems through an automata-theoretic Lens
- Distributed degree splitting, edge coloring, and orientations
- An exponential separation between randomized and deterministic complexity in the LOCAL model
- New classes of distributed time complexity
- A lower bound for the distributed Lovász local lemma
- LCL problems on grids
- How much does randomness help with locally checkable problems?
- Sublogarithmic distributed algorithms for Lovász local lemma, and the complexity hierarchy
- Brief Announcement: Classification of Distributed Binary Labeling Problems
- The Distributed Complexity of Locally Checkable Problems on Paths is Decidable
- Almost global problems in the LOCAL model
Cited In (2)
This page was built for publication: Distributed graph problems through an automata-theoretic lens
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2689441)
