The Distributed Complexity of Locally Checkable Problems on Paths is Decidable

DOI10.1145/3293611.3331606OpenAlexW2963024304MaRDI QIDQ5145218

Jukka Suomela, Dennis Olivetti, Sebastian F. Brandt, Yi-Jun Chang, Mikaël Rabie, Alkida Balliu

Publication date: 20 January 2021

Published in: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1811.01672

zbMATH Keywords

complexitydecidabilitydistributed computing

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Related Items (3)

Locally checkable problems in rooted trees ⋮ Distributed graph problems through an automata-theoretic lens ⋮ Distributed graph problems through an automata-theoretic Lens

This page was built for publication: The Distributed Complexity of Locally Checkable Problems on Paths is Decidable