Computations on Nondeterministic Cellular Automata
| dc.creator | Ozhigov, Yuri | |
| dc.date | 1998-01-16 | |
| dc.date.accessioned | 2026-07-07T02:36:22Z | |
| dc.date.available | 2026-07-07T02:36:22Z | |
| dc.description | 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. | |
| dc.description | 18 pages in AmsTex, 3 figures in PostScript | |
| dc.identifier | https://arxiv.org/abs/comp-gas/9801001 | |
| dc.identifier | http://arxiv.org/abs/comp-gas/9801001 | |
| dc.identifier | Information and Computation 148, 181-201 (1999) | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/15896 | |
| dc.subject | Cellular Automata and Lattice Gases | |
| dc.title | Computations on Nondeterministic Cellular Automata | |
| dc.type | text |