2014/04/25 by Reiter, Fabian
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic in Computer Science (cs.LO)
paper · doi:10.48550/arxiv.1404.6503
Inspired by distributed algorithms, we introduce a new class of finite graph automata that recognize precisely the graph languages definable in monadic second-order logic. For the cases of words and trees, it has been long known that the regular languages are precisely those definable in monadic second-order logic. In this regard, the automata proposed in the present work can be seen, to some extent, as a generalization of finite automata to graphs. Furthermore, we show that, unlike for finite automata on words and trees, the deterministic, nondeterministic and alternating variants of our automata form a strict hierarchy with respect to their expressive power. For the weaker variants, the emptiness problem is decidable.