ALTERNATION ON CELLULAR-AUTOMATA

In this paper we consider several notions of alternation in cellular a utomata: non-uniform, uniform and weak alternation. We study relations among these notions and with alternating Turing machines. It is prove d that the languages accepted in polynomial time by alternating Turing machines are those accepted by alternating cellular automata in polyn omial time for all the proposed alternating cellular automata. In part icular, this is true for the weak model where the difference between e xistential and universal states is omitted for all the cells except th e first one. It is proved that real time alternation in cellular autom ata is strictly more powerful than real time alternation in Turing mac hines, with only one read-write tape. Moreover, it is shown that in li near time uniform and weak models agree.