Computations on Nondeterministic Cellular Automata

This work concerns the trade-offs between the dimension and the time and space complexity of computations on nondeterministic cellular automata. We assume that the space complexity is the diameter of area in space involved in computation. It is proved that (1) every nondeterministic cellular automata (NCA) A of dimensionr, computing a predicatePwith time complexityT(n) and space complexityS(n) can be simulated byr-dimensional NCA with time and space complexityO(T 1/(r+1) S r/(r+1)) and byr+1 dimensional NCA with time and space complexityO(T 1/2+S), whereTandSare functions constructible in time, (2) for any predicatePand integerr>1 if A is a fastestr-dimensional NCA computingPwith time complexityT(n) and space complexityS(n), thenT=O(S), and (3) ifT r, P is the time complexity of a fastestr-dimensional NCA computing predicatePthenT r+1, P =O((T r, P )1−r/(r+1)2 ), T r+1, P =O((T r, P )1+2/r ). Similar problems for deterministic cellular automata (CA) are discussed.

Authors

• Yuri Ozhigov

Keywords

No keywords are indexed for this paper.