Simulations Between Multi-dimensional Deterministic and Alternating Cellular Automata

Issue title: Cellular Automata

Article type: Research Article

Authors: Iwamoto, Chuzo | Tateishi, Katsuyuki^; | Morita, Kenichi | Imai, Katsunobu

Affiliations: Graduate School of Engineering, Higashi-Hiroshima, 739-8527, Japn | NTT Comware Corporation, Tokyo, 108-8019, Japan

Abstract: We present simulation and separation results between multi-dimensional deterministic and alternating cellular automata (CAs). It is shown that for any integers k≥l≥1, every k-dimensional t(n)-time deterministic CA can be simulated by an l-dimensional O(t(n)^{(k-l+1)/(k-l+2}))-time alternating CA. This result is a dimension reduction theorem and also a time reduction theorem: (i) Every multi-dimensional deterministic CA can be simulated by a one-dimensional alternating CA without increasing time complexity. (ii) Every deterministic computation in a multi-dimensional deterministic CA can be sped up quadratically by alternations when the dimension is fixed. Furthermore, it is shown that there is a language which can be accepted by a one-dimensional alternating CA in t(n) time but not by any multi-dimensional deterministic CA in t(n) time.

Keywords: cellular automata, alternation, simulation, separation

Journal: Fundamenta Informaticae, vol. 58, no. 3-4, pp. 261-271, 2003