Communication Complexity for Asynchronous Systems of
Finite Devices
Tomasz Jurdzinski, Miroslaw Kutylowski, Jan Zatopianski
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 Omega(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 that LTRANS can be recognized with O(n) messages by a synchronous
system of finite automata, we show that LTRANS
requires Omega(n^{3/2}/
log^2 n) messages on any asynchronous system.