Relativised cellular automata and complexity classes

Some of the fundamental problems concerning cellular automata (CA) are as follows:1) Are linear-time CA UCA) more powerful than real-time CA (rCA)? 2) Are nonlinear-time CA more powerful than linear-time CA? 3) Does one-way communication reduce the power of a CA? These questions have been open for a long time. In this paper, we address these questions with respect to tally languages in relativised worlds, interpreting time-varying CA (TVCA) as oracle machines. We construct a) oracles which separate rCA from 1CA and iCA from CA, b) oracle classes under which the CA classes coincide, and c) oracles which leave the CA classes unchanged. Further, with rCA and iCA at the base, we build a hierarchy of relativised CA complexity classes between rCA and CA, and study the dependencies between the classes in this hierarchy.