Message complexity for unary multiautomata systems

Christian Choffrut

Finitely many two-way automata work independently and synchronously on a unary input. Some of their states are broadcasting, i.e., dispatched to all other automata. At each step of…