Surjective multidimensional cellular automata are non-wandering: A combinatorial proof

被引：10

作者：

Acerbi, Luigi ^{[1
]}

Dennunzio, Alberto ^{[2
]}

Formenti, Enrico ^{[3
]}

机构：

[1] Univ Edinburgh, DTC Neuroinformat & Computat Neurosci, Sch Informat, Edinburgh EH8 9AB, Midlothian, Scotland

[2] Univ Milano Bicocca, Dipartimento Informat Sistemist & Comunicaz, I-20126 Milan, Italy

[3] Univ Nice Sophia Antipolis, Lab I3S, F-06903 Sophia Antipolis, France

来源：

INFORMATION PROCESSING LETTERS | 2013年 / 113卷 / 5-6期

关键词：

Combinatorial problems; Multidimensional cellular automata; Symbolic dynamics; Discrete dynamical systems; EQUICONTINUITY; POINTS;

D O I：

10.1016/j.ipl.2012.12.009

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

A combinatorial proof that surjective D-dimensional CA are non-wandering is given. This answers an old open question stated in Blanchard and Tisseur (2000) [3]. Moreover, an explicit upper bound for the return time is given. (C) 2013 Elsevier B.V. All rights reserved.

引用

页码：156 / 159

页数：4