CS Forum: "Asynchronous Distributed Automata: A Characterization of the Modal Mu-Fragment"

2018-05-24 14:15:00 2018-05-24 15:00:00 Europe/Helsinki CS Forum: "Asynchronous Distributed Automata: A Characterization of the Modal Mu-Fragment" CS forum is a seminar series arranged at the CS department - open to everyone free-of-charge. http://cs.aalto.fi/en/midcom-permalink-1e8538f5199486e538f11e8987419bb9e1455605560 Konemiehentie 2, 02150, Espoo

CS forum is a seminar series arranged at the CS department - open to everyone free-of-charge.

24.05.2018 / 14:15 - 15:00
lecture room T3, Konemiehentie 2, 02150, Espoo, FI

Fabian Reiter
Post-doctoral researcher
LSV, Université Paris-Saclay

Host: Professor Jukka Suomela
Time: 14:15 (coffee at 14:00)
Venue: T3, CS building

Asynchronous Distributed Automata: A Characterization of the Modal Mu-Fragment

Abstract:

I will present 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
considered logic is (a variant of) the fragment of modal μ-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. As a by-product, the connection with logic also entails that the expressive power of those machines is independent of whether or not messages can be lost.

The paper this talk is about won the best student paper prize at ICALP 2017: https://arxiv.org/abs/1611.08554

Speaker bio:

  • 2018: Postdoc @ LSV, University of Paris-Saclay.
  • 2014 – 2017: PhD @ IRIF (LIAFA), Paris Diderot University.
  • 2011 – 2014: Master of Science @ University of Freiburg.
  • 2007 – 2010: Bachelor of Science @ Free University of Berlin.