Header menu link for other important links
Relativised cellular automata and complexity classes
Kamala Krithivasan
Published in Springer Verlag
Volume: 560 LNCS
Pages: 172 - 185
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. © Springer-Verlag Berlin Heidelberg 1991.
About the journal
JournalData powered by TypesetLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherData powered by TypesetSpringer Verlag
Open AccessNo
Concepts (7)
  •  related image
    Computational complexity
  •  related image
    Software engineering
  •  related image
    Complexity class
  •  related image
    Linear time
  •  related image
    Real time
  •  related image
    Time varying
  •  related image
    Cellular automata