Communication complexity for asynchronous systems of finite devices
Tomasz Jurdziński, Mirosław Kutyłowski, Jan Zatopiański · 2005
We consider systems consisting of a constant number of finite automata communicating via messages. We assume that the automata are asynchronous, but the answers given by the system must be always correct. We examine computational power of such systems by inspecting the number of messages exchanged. This is motivated by the fact that communication volume is one of the most important complexity measures. We show that any asynchronous system of finite automata that exchanges o(n) messages is able to recognize regular languages only. This is much different than in the case of synchronous systems considered before (where already a constant number of messages suffices to recognize some non-regular languages). We show that asynchronous and synchronous systems may differ significantly in their computational power also for tasks requiring ( n) messages. We consider a language Ltrans consisting of words of the form A#A T , where A T denotes transposition of matrix A and the matrices are written row by row. While it is easy to see thatLtrans can be recognized withO(n) messages by a synchronous system of finite automata, we show thatLtrans requires ( n 3=2 = log 2 n) messages on any asynchronous system.