2026-07-23T08:19:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7369 2024-03-06T10:40:29Z ddc:004 open_access

Asynchronous Distributed Automata: A Characterization of the Modal Mu-Fragment Reiter, Fabian finite automata distributed computing modal logic mu-calculus We establish the equivalence between a class of asynchronous distributed automata and a small fragment of least fixpoint logic, when restricted to finite directed graphs. More specifically, the logic we consider is (a variant of) the fragment of the modal mu-calculus that allows least fixpoints but forbids greatest fixpoints. The corresponding automaton model uses a network of identical finite-state machines that communicate in an asynchronous manner and whose state diagram must be acyclic except for self-loops. Exploiting the connection with logic, we also prove that the expressive power of those machines is independent of whether or not messages can be lost. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Fabian Reiter 2017 Is Part Of LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2017.100 urn:nbn:de:0030-drops-73695 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.100 eng https://creativecommons.org/licenses/by/3.0/legalcode