Distributed graph problems through an automata-theoretic Lens
type: Item
instance of: scholarly article
title: Distributed graph problems through an automata-theoretic Lens
DOI: 10.1007/978-3-030-79527-6_3
author: Yi-Jun Chang
author: Jan Studený
author: Jukka Suomela
publication date: 2022-03-22T00:00:00Z
full work available at URL: https://arxiv.org/abs/2002.07659
Mathematics Subject Classification ID: 68Mxx
Mathematics Subject Classification ID: 68Q11
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 7495132
MaRDI profile type: Publication
OpenAlex ID: W3128447208
cites work: The Distributed Complexity of Locally Checkable Problems on Paths is Decidable
cites work: Brief Announcement: Classification of Distributed Binary Labeling Problems
cites work: Almost global problems in the LOCAL model
cites work: How much does randomness help with locally checkable problems?
cites work: New classes of distributed time complexity
cites work: The Locality of Distributed Symmetry Breaking
cites work: A lower bound for the distributed Lovász local lemma
cites work: LCL Problems on Grids
cites work: Q5509690
cites work: An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model
cites work: A Time Hierarchy Theorem for the LOCAL Model
cites work: Deterministic coin tossing with applications to optimal parallel list ranking
cites work: Synchronizing non-deterministic finite automata
cites work: Reset Sequences for Monotonic Automata
cites work: Improved upper bounds on synchronizing nondeterministic automata
cites work: Distributed Degree Splitting, Edge Coloring, and Orientations
cites work: Q5696194
cites work: Directable nondeterministic automata
cites work: Locality in Distributed Graph Algorithms
cites work: Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
cites work: What Can be Computed Locally?
cites work: Distributed Computing: A Locality-Sensitive Approach
cites work: Distributed coloring algorithms for triangle-free graphs
cites work: Polylogarithmic-time deterministic network decomposition and distributed derandomization
cites work: Q4131648
cites work: Sublogarithmic distributed algorithms for Lovász local lemma, and the complexity hierarchy
description: scientific article; zbMATH DE number 7495132