Nonlinear Sciences – Cellular Automata and Lattice Gases
Scientific paper
1998-01-16
Information and Computation 148, 181-201 (1999)
Nonlinear Sciences
Cellular Automata and Lattice Gases
18 pages in AmsTex, 3 figures in PostScript
Scientific paper
The work is concerned with the trade-offs between the dimension and the time and space complexity of computations on nondeterministic cellular automata. It is proved, that 1). Every NCA $\Cal A$ of dimension $r$, computing a predicate $P$ with time complexity T(n) and space complexity S(n) can be simulated by $r$-dimensional NCA with time and space complexity $O(T^{\frac{1}{r+1}} S^{\frac{r}{r+1}})$ and by $r+1$-dimensional NCA with time and space complexity $O(T^{1/2} +S)$. 2) For any predicate $P$ and integer $r>1$ if $\Cal A$ is a fastest $r$-dimensional NCA computing $P$ with time complexity T(n) and space complexity S(n), then $T= O(S)$. 3). If $T_{r,P}$ is time complexity of a fastest $r$-dimensional NCA computing predicate $P$ then $T_{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 CA are discussed.
No associations
LandOfFree
Computations on Nondeterministic Cellular Automata does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Computations on Nondeterministic Cellular Automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computations on Nondeterministic Cellular Automata will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-224722