Title :
Distributed Graph Automata
Author_Institution :
LIAFA, Univ. Paris, Paris, France
Abstract :
Combining ideas from distributed algorithms and alternating automata, we introduce a new class of finite graph automata that recognize precisely the languages of finite graphs definable in monadic second-order logic. By restricting transitions to be nondeterministic or deterministic, we also obtain two strictly weaker variants of our automata for which the emptiness problem is decidable.
Keywords :
decidability; distributed algorithms; finite automata; graph theory; alternating automata; decidability; distributed algorithms; distributed graph automata; emptiness problem; finite graph automata; finite graphs languages; monadic second-order logic; Automata; Color; Computer science; Distributed algorithms; Indexes; Standards; Terminology; Finite automata; Graphs; MSO-logic;
Conference_Titel :
Logic in Computer Science (LICS), 2015 30th Annual ACM/IEEE Symposium on
Conference_Location :
Kyoto
DOI :
10.1109/LICS.2015.27
