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.