Computations on Nondeterministic Cellular Automata

AbstractThis 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(T1/(r+1)Sr/(r+1)) and byr+1 dimensional NCA with time and space complexityO(T1/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) ifTr,Pis the time complexity of a fastestr-dimensional NCA computing predicatePthenTr+1,P=O((Tr, P)1−r/(r+1)2),Tr+1,P=O((Tr, P)1+2/r).Similar problems for deterministic cellular automata (CA) are discussed