Some results on time-varying and relativised cellular automata. (English) Zbl 0761.68068

Summary: Cellular automata (CA) are parallel language recognition devices. 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. 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.


68Q80 Cellular automata (computational aspects)
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
Full Text: DOI


[1] Bucher W., RAIRO Inform. Theor. 18 pp 307– (1984)
[2] DOI: 10.1007/BF00264617 · Zbl 0534.68039 · doi:10.1007/BF00264617
[3] DOI: 10.1145/44483.44493 · doi:10.1145/44483.44493
[4] DOI: 10.1016/S0019-9958(80)90164-3 · Zbl 0442.68082 · doi:10.1016/S0019-9958(80)90164-3
[5] DOI: 10.1016/0304-3975(88)90040-0 · Zbl 0646.68071 · doi:10.1016/0304-3975(88)90040-0
[6] Ibarra O., SIAM J. Comput 16 pp 46– (1987)
[7] DOI: 10.1016/0743-7315(85)90034-6 · doi:10.1016/0743-7315(85)90034-6
[8] Krithivasan, K. and Das, A. Treating terminals as function values of time.Proceedings of the 4th FST & TCS conference, LNCS. Vol. 181, pp.188–201. · Zbl 0554.68049
[9] DOI: 10.1016/0734-189X(85)90015-5 · Zbl 0622.68067 · doi:10.1016/0734-189X(85)90015-5
[10] DOI: 10.1080/00207168608803509 · Zbl 0655.68102 · doi:10.1080/00207168608803509
[11] DOI: 10.1080/00207168808803646 · Zbl 0658.68096 · doi:10.1080/00207168808803646
[12] DOI: 10.1109/T-C.1974.223995 · Zbl 0285.68027 · doi:10.1109/T-C.1974.223995
[13] Mahajan, Meena and Krithivasan, Kamala. 1991. Relativised cellular automata and complexity classes, Technical Report, Dept. of Computer Science, IIT Madras, Nov 90.LNCS Proceedings of the 11th FST & TCS conference. December1991, New Delhi. to appear · Zbl 0925.68328
[14] DOI: 10.1007/BF01744290 · Zbl 0422.68019 · doi:10.1007/BF01744290
[15] Salomaa, A. 1973. ”Formal Languages”. Academic Press. · Zbl 0262.68025
[16] DOI: 10.1016/S0019-9958(71)90501-8 · Zbl 0222.94057 · doi:10.1016/S0019-9958(71)90501-8
[17] DOI: 10.1016/S0022-0000(72)80004-7 · Zbl 0268.68044 · doi:10.1016/S0022-0000(72)80004-7
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.