Simulations Between Multi-dimensional Deterministic and Alternating Cellular Automata

• Autorzy: Iwamoto C. , Tateishi K. , Morita K. , Imai K.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

cellular automata; alternation; simulation; separation

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2003
• Tom: Vol. 58, nr 3,4
• Strony: 261--271
• Opis fizyczny: bibliogr. 26 poz.

Twórcy

autor

Iwamoto C.

autor

Tateishi K.

autor

Morita K.

autor

Imai K.

• Graduate School of Engineering, Higashi-Hiroshima, 739-8527, Japan,