Asynchronous automata, trees, and reconfigurability

Prelegent(ci)

Mathieu Lehaut

Afiliacja

University of Warsaw

Język referatu

angielski

Termin

23 kwietnia 2025 14:15

Pokój

p. 5440

Tytuł w języku polskim

Asynchronous automata, trees, and reconfigurability

Seminarium

Seminarium „Teoria automatów”

---

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.

---