Adding Reconfiguration to Zielonka's Asynchronous Automata
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913114290651136 |
|---|---|
| author | Lehaut, Mathieu Piterman, Nir |
| author_facet | Lehaut, Mathieu Piterman, Nir |
| contents | We study an extension of Zielonka's (fixed) asynchronous automata called reconfigurable asynchronous automata where processes can dynamically change who they communicate with. We show that reconfigurable asynchronous automata are not more expressive than fixed asynchronous automata by giving translations from one to the other. However, going from reconfigurable to fixed comes at the cost of disseminating communication (and knowledge) to all processes in the system. We then show that this is unavoidable by describing a language accepted by a reconfigurable automaton such that in every equivalent fixed automaton, every process must either be aware of all communication or be irrelevant. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_01425 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Adding Reconfiguration to Zielonka's Asynchronous Automata Lehaut, Mathieu Piterman, Nir Formal Languages and Automata Theory We study an extension of Zielonka's (fixed) asynchronous automata called reconfigurable asynchronous automata where processes can dynamically change who they communicate with. We show that reconfigurable asynchronous automata are not more expressive than fixed asynchronous automata by giving translations from one to the other. However, going from reconfigurable to fixed comes at the cost of disseminating communication (and knowledge) to all processes in the system. We then show that this is unavoidable by describing a language accepted by a reconfigurable automaton such that in every equivalent fixed automaton, every process must either be aware of all communication or be irrelevant. |
| title | Adding Reconfiguration to Zielonka's Asynchronous Automata |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2305.01425 |