Name
Title | ||
|---|---|---|
An Exact Solution to the Two-Dimensional Arbitrary-Threshold Density Classification Problem. |
Abstract | ||
|---|---|---|
Density classification is one of the most studied cellular automata problems. As initially presented [5], it does not have an exact solution [7]. However, [2] and [4] demonstrate that a simple change in the proposed accepting condition makes such a solution easily achievable for one-dimensional cellular automata. We show not only that a similar result is possible for two-dimensional cellular automata, but also that this result can be obtained in O(root n) expected running time (where n is the total number of cells in the automaton), compared to an O(n) running time for the one-dimensional case - thus answering an open problem presented in [1]. Our proposed automaton is also capable of classifying arbitrary density thresholds (not just 1/2). |
Year | Venue | Keywords |
|---|---|---|
2009 | JOURNAL OF CELLULAR AUTOMATA | Cellular automata,arbitrary density classification,majority,two dimensions,rule 184,gravity |
Field | DocType | Volume |
Exact solutions in general relativity,Applied mathematics,Discrete mathematics,Mathematics | Journal | 4 |
Issue | ISSN | Citations |
3 | 1557-5969 | 0 |
PageRank | References | Authors |
0.34 | 0 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sami Torbey | 1 | 17 | 3.36 |
| Selim G. Akl | 2 | 2074 | 299.32 |