Language classes defined by time-bounded relativised cellular automata
Meena Mahajan, Kamala Krithivasan · RAIRO - Theoretical Informatics and Applications · 1993
Some of the fundamental problems concerning cellular automata {CA) are asfollows: -Are Hnear-time CA {ICA) more powerfuî thon real-time CA(rCA)?-Are nonlinear-time CA more powerfuî thon Hnear-time CA ?-Does one-way communication reduce the power of a CA ?These question have been open for a long time.In this paper\ we address these questions with respect to tally languages in relativised worlds, interpreting timevarying CA (TVCA) as oracle machines.We construct -oracles which separate rCAfrom IC A and ICAfrom CA, -oracle classes under which the CA classes coincide, and -oracles which leave the CA classes unchanged.Further, with r CA and IC A 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.