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.