Computations on Nondeterministic Cellular Automata |
| |
Authors: | Yuri Ozhigov |
| |
Affiliation: | Department of Mathematics, Moscow State Technological University “Stankin,” Vadkovsky per. 3a, 101472, Moscow, Russiaf1 |
| |
Abstract: | 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) 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 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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|