Distributed graph automata

DOI10.1109/LICS.2015.27MaRDI QIDQ4635803zbMATH OpenOpenAlexFDO

Authors 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)

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)

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.

Recommendations

• Emptiness problems for distributed automata
• Emptiness problems for distributed automata
• Nondeterminism versus determinism of finite automata over directed acyclic graphs
• scientific article; zbMATH DE number 3858446
• Finite automata on directed graphs

Cited in

(21)

• scientific article; zbMATH DE number 1839464 (Why is no real title available?)
• Relating paths in transition systems: the fall of the modal mu-calculus
• scientific article; zbMATH DE number 1701347 (Why is no real title available?)
• Communicating finite-state machines, first-order logic, and star-free propositional dynamic logic
• A hierarchy of local decision
• Networks of Automata: Some Applications
• Asynchronous distributed automata: a characterization of the modal \(\mu\)-fragment
• Constant space and non-constant time in distributed computing
• Distributed ω-Automata
• Emptiness problems for distributed automata
• What can be verified locally?
• Automata on Directed Graphs: Edge Versus Vertex Marking
• scientific article; zbMATH DE number 2086633 (Why is no real title available?)
• The tree width of auxiliary storage
• Identifiers in registers. Describing network algorithms with logic
• Communicating finite-state machines and two-variable logic
• Brief announcement: Distributed graph problems through an automata-theoretic lens
• Nondeterminism versus determinism of finite automata over directed acyclic graphs
• Cooperating Distributed Tree Automata
• scientific article; zbMATH DE number 219260 (Why is no real title available?)
• Emptiness problems for distributed automata

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)