Brief announcement: Distributed graph problems through an automata-theoretic lens

DOI10.4230/lipics.disc.2020.41zbMATH Open1540.68303MaRDI QIDQ6535040

Jukka Suomela, Jan Studený, Yi-Jun Chang

Publication date: 2 November 2023

zbMATH Keywords

localitynondeterministic finite automataalgorithm synthesisLOCAL modeldistributed computational complexitylocally checkable labeling problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Cites Work

• What Can be Computed Locally?
• The Distributed Complexity of Locally Checkable Problems on Paths is Decidable
• LCL Problems on Grids

This page was built for publication: Brief announcement: Distributed graph problems through an automata-theoretic lens