Stochastic Cellular Automata Solutions to the Density Classification ProblemWhen Randomness Helps Computing

被引：0

作者：

Nazim Fatès

机构：

[1] Nancy Université,INRIA Nancy—Grand Est, LORIA

来源：

Theory of Computing Systems | 2013年 / 53卷

关键词：

Stochastic and probabilistic cellular automata; Density classification problem; Models of spatially distributed computing; Stochastic process;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

In the density classification problem, a binary cellular automaton (CA) should decide whether an initial configuration contains more 0s or more 1s. The answer is given when all cells of the CA agree on a given state. This problem is known for having no exact solution in the case of binary deterministic one-dimensional CA.

引用

页码：223 / 242

页数：19