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.