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.
Get full access to this article
View all access options for this article.