Distributed Graph Automata

DOI10.1109/LICS.2015.27zbMATH Open1401.68166arXiv1404.6503OpenAlexW3103882277MaRDI QIDQ4635803FDOQ4635803

Fabian Reiter

Publication date: 23 April 2018

Published in: 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Abstract: 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.

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Automata and formal grammars in connection with logical questions (03D05)

Cited In (14)

• Communicating finite-state machines, first-order logic, and star-free propositional dynamic logic
• A hierarchy of local decision
• Distributed ω-Automata
• Title not available (Why is that?)
• Communicating Finite-State Machines and Two-Variable Logic
• Constant space and non-constant time in distributed computing
• Nondeterminism versus determinism of finite automata over directed acyclic graphs
• What can be verified locally?
• Cooperating Distributed Tree Automata
• Title not available (Why is that?)
• Title not available (Why is that?)
• Emptiness problems for distributed automata
• Relating Paths in Transition Systems: The Fall of the Modal Mu-Calculus
• Title not available (Why is that?)

This page was built for publication: Distributed Graph Automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635803)