Multi-party Finite Computations 
Tomasz Jurdzinski, Miroslaw Kutylowski and Krzysztof Lorys

We consider systems consisting of a finite  number  of  finite  automata
which  communicate  by  sending messages. We consider number of messages
necessary to recognize  a  language  as  a  complexity  measure  of  the
language.  We  feel  that  these  considerations give a new insight into
computational complexity of problems computed by  read-only  devices  in
multiprocessor  systems.  Our  considerations are related to multi-party
communication complexity, but we make a realistic assumption  that  each
party has a limited memory.

We show a number of hierarchy results for this complexity  measure:  for
each  constant  k  there is a language, which may be recognized with k+1
messages and cannot be recognized with k-1 messages. We give an  example
of  a  language  that  requires Theta(log log n) messages and claim that
Omega(log log(n)) messages are necessary, if a  language  requires  more
than  a constant number of messages. We present a language that requires
Theta(n) messages. For a large family of functions  f,  f(n)=  omega(log
log  n)  ,  f(n)=o(n) , we prove that there is a language which requires
Theta(f(n))  messages.  Finally,  we  present  functions  that   require
omega(n) messages.