2024/08/20 by Daniel Hausmann, Hausmann, Daniel, Mathieu Lehaut +3
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · #DNA and Biological Computing #Embedded Systems Design Techniques #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Modular Robots and Swarm Intelligence
paper · pdf · doi:10.48550/arxiv.2408.10708
openalex publication_date 2024/08/20 · openalex created_date 2024/10/01 · openalex updated_date 2026/07/28
We study how to distribute trace languages in a setting where processes communicate via reconfigurable communication channels. That is, the different processes can connect and disconnect from channels at run time. We restrict attention to communication via tree-like communication architectures. These allow channels to connect more than two processes in a way that maintains an underlying spanning tree and keeps communication continuous on the tree. We make the reconfiguration explicit in the language allowing both a centralized automaton as well as the distributed processes to share relevant information about the current communication configuration. We show that Zielonka's seminal result regarding distribution of regular languages for asynchronous automata can be generalized in this setting, incorporating both reconfiguration and more than binary tree architectures.