Emptiness problems for distributed automata

DOI10.1016/J.IC.2019.104503MaRDI QIDQ2182732zbMATH OpenOpenAlexWikidataFDO

Authors Antti Kuusisto, Fabian Reiter

Publication date 26 May 2020

Published in Information and Computation (Search for Journal in Brave)

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

zbMATH Keywords

distributed computingemptiness problemfinite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Abstract: We investigate the decidability of the emptiness problem for three classes of distributed automata. These devices operate on finite directed graphs, acting as networks of identical finite-state machines that communicate in an infinite sequence of synchronous rounds. The problem is shown to be decidable in LogSpace for a class of forgetful automata, where the nodes see the messages received from their neighbors but cannot remember their own state. When restricted to the appropriate families of graphs, these forgetful automata are equivalent to classical finite word automata, but strictly more expressive than finite tree automata. On the other hand, we also show that the emptiness problem is undecidable in general. This already holds for two heavily restricted classes of distributed automata: those that reject immediately if they receive more than one message per round, and those whose state diagram must be acyclic except for self-loops.

Recommendations

• Emptiness problems for distributed automata
• Distributed graph automata
• scientific article; zbMATH DE number 1759634
• Distributed ω-Automata
• Probabilistic automata on finite words: decidable and undecidable problems

Cites work

• Asynchronous distributed automata: a characterization of the modal \(\mu\)-fragment
• Basics on tree automata
• Cellular automata -- a computational point of view
• Cellular automata with sparse communication
• Counter machines and distributed automata -- a story about exchanging space and time
• Datalog and constraint satisfaction with infinite templates
• Decidability of parameterized verification
• Distributed graph automata
• Handbook of modal logic
• scientific article; zbMATH DE number 3718546 (Why is no real title available?)
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• Infinite networks, halting and local algorithms
• Locally checkable proofs in distributed computing
• Modal logic and distributed message passing automata
• Ontology-based data access: a study through disjunctive Datalog, CSP, and MMSNP
• Rewritability in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics (Invited Talk).
• Survey of local algorithms
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Weak models of distributed computing, with connections to modal logic
• Weak models of distributed computing, with connections to modal logic

Cited in

(6)

• Emptiness Under Isolation and the Value Problem for Hierarchical Probabilistic Automata
• Emptiness problems for distributed automata
• Distributed graph automata
• The tree width of auxiliary storage
• Distributed ω-Automata
• Undecidability of the emptiness problem for weak models of distributed computing

This page was built for publication: Emptiness problems for distributed automata

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