Cellular Automata Complexity Trade-Offs
Cellular Automata Complexity Trade-Offs
复制标题
元胞自动机复杂性权衡
DOI：
10.1016/s0019-9958(71)90501-8
复制
发表时间：
1971
期刊：
影响因子：
--
通讯作者：
A. R. Smith
中科院分区：
文献类型：
--
作者：
A. R. Smith
研究元胞自动机的一般理论，特别注意结构的复杂性。特别地，通过元胞自动机模拟元胞自动机来明确邻域大小和状态集基数之间的权衡关系。建立了一维元胞自动机的最小邻域模板（d+ 1个元素）。该类的最小状态集显示为二进制状态集。结构复杂性权衡的时间成本（如果有的话）也进行了研究。证明了任何线性时间成本都可以消除，事实上，在增加结构成本的情况下，可以获得任意正整数因子的加速。
The general theory of cellular automata is investigated with special attention to structural complexity. In particular, simulation of cellular automata by cellular automata is used to make explicit trade-off relationships between neighborhood size and state-set cardinality. A minimum neighborhood template withd+ 1 elements is established for the class ofd-dimensional cellular automata. The minimum state set for this class is shown to be the binary state set. The temporal costs, if any, of structural complexity trade-offs are also studied. It is demonstrated that any linear time cost can be eliminated and, in fact, a speed-up by arbitrary positive integer factorkcan be attained at an increased structural cost.