Header menu link for other important links
X
Some Results On Time-Varying And Relativised Cellular Automata
Kamala Krithivasan
Published in
1992
Volume: 43
   
Issue: 1-2
Pages: 21 - 38
Abstract
Cellular automata (CA) are parallel language recognition devices. In this paper, the notion of a time-varying CA (TVCA) is introduced. In a TVCA, the transition function can vary with time, and the variation is controlled by a prespecified language. This language can be viewed as an oracle to which the TVCA makes implicit queries; thus TVCA provide a mechanism for defining relativised CA. In this paper, the recognition capabilities of CA and TVCA are compared. TVCA as relativised CA are formalised, and the power of this implicit query mechanism is compared with the traditional oracle access in Turing machines. © 1992, Taylor & Francis Group, LLC. All rights reserved.
About the journal
JournalInternational Journal of Computer Mathematics
ISSN00207160
Open AccessNo