2026-07-22T10:24:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13119 2024-03-06T10:51:36Z ddc:004 open_access

Brief Announcement: Distributed Graph Problems Through an Automata-Theoretic Lens Chang, Yi-Jun Studený, Jan Suomela, Jukka Algorithm synthesis locally checkable labeling problems LOCAL model locality distributed computational complexity nondeterministic finite automata We study the following algorithm synthesis question: given the description of a locally checkable graph problem Π for paths or cycles, determine in which instances Π is solvable, determine what is the locality of Π, and construct an asymptotically optimal distributed algorithm for solving Π (in the usual LOCAL model of distributed computing). To answer such questions, we represent Π as a nondeterministic finite automaton ℳ over a unary alphabet, and identify polynomial-time-computable properties of automaton ℳ that capture the locality and solvability of problem Π. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yi-Jun Chang and Jan Studený and Jukka Suomela 2020 Is Part Of LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2020.41 urn:nbn:de:0030-drops-131197 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.41 eng https://creativecommons.org/licenses/by/3.0/legalcode