文章基本信息

标题：Brief Announcement: Distributed Graph Problems Through an Automata-Theoretic Lens
本地全文：下载
作者：Yi-Jun Chang ; Jan Studený ; Jukka Suomela 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：179
页码：1-3
DOI：10.4230/LIPIcs.DISC.2020.41
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 Î .
关键词：Algorithm synthesis; locally checkable labeling problems; LOCAL model; locality; distributed computational complexity; nondeterministic finite automata