Asynchronous automata, trees, and reconfigurability

Speaker(s)

Mathieu Lehaut

Affiliation

University of Warsaw

Language of the talk

English

Date

April 23, 2025, 2:15 p.m.

Room

room 5440

Title in Polish

Asynchronous automata, trees, and reconfigurability

Seminar

Seminar Automata Theory

---

I will present some results about Zielonka's asynchronous automata, 
which are a popular automata model for concurrent programs.

Zielonka's seminal result about distributivity shows that one can go 
from a centralized specification given by a DFA to a distributed 
implementation given by an asynchronous automaton. This result has been 
well-studied, and new constructions have been made for restricted cases 
of communication architectures (who can communicate with who). In 
particular, when the communication architecture is a tree, there is a 
simple and efficient construction.
Another interesting problem is about control, i.e. whether we can, in a 
game-like setting with controllable System actions and uncontrollable 
Environment actions, find a winning controller for the System. The 
control problem has been shown to be decidable for tree architectures.
I will show that those two problems can be solved for a more general 
class of architectures we call tree-like.

Finally, I will introduce reconfigurable asynchronous automata, an 
extension in which the communication architecture can change dynamically 
during an execution.
Then I will show that the construction for the tree-like distributivity 
problem can be extended to this setting.

---