Name
Abstract | ||
|---|---|---|
We study the computational complexity of the evolution of configurations on finite and infinite cellular automata. We will show that a classification of cellular automata suggested by Culik and Yu and based on Wolfram's earlier heuristic classification leads to classes that are II
2
0
-complete and is
3
0
-complete. |
Year | DOI | Venue |
|---|---|---|
1989 | 10.1007/3-540-51498-8_44 | FCT |
Keywords | Field | DocType |
computational complexity,cellular automata | Cellular automaton,Discrete mathematics,Heuristic,Computer science,Theoretical computer science,Turing machine,Computational resource,Computational complexity theory | Conference |
ISBN | Citations | PageRank |
3-540-51498-8 | 2 | 0.52 |
References | Authors | |
4 | 1 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Klaus Sutner | 1 | 119 | 19.42 |