Power of Cooperation and Multihead Finite Systems
 
 Pavol Duris, Tomasz Jurdzinski, Miroslaw Kutylowski, Krzysztof Lorys

We consider systems of finite automata performing  together  computation
on  an  input  string.  Each  automaton has its own read head that moves
independently of the other heads, but the automata cooperate  in  making
state  transitions.  Computational  power of such devices depends on the
number of states of automata, the number of automata, and the  way  they
cooperate.  We  concentrate  our  attention on the last issue. The first
situation that we consider is that each automaton has a  full  knowledge
on  the states of all automata ( multihead automata ). The other extreme
is that each automaton (called also a processor ) has no \mbox knowledge
of  the  states of other automata; merely, there is a central processing
unit that may ``freeze'' any automaton or let it proceed  its  work  (so
called  multiprocessor automata ). The second model seems to be severely
restricted, but we show that multihead and multiprocessor automata  have
similar computational power. Nevertheless, we show a separation result.