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
相关论文
共 50 条
  • [1] Bounds on Non-surjective Cellular Automata
    Kari, Jarkko
    Vanier, Pascal
    Zeume, Thomas
    MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2009, 2009, 5734 : 439 - +
  • [2] Homogeneity of surjective cellular automata
    Moothathu, TKS
    DISCRETE AND CONTINUOUS DYNAMICAL SYSTEMS, 2005, 13 (01) : 195 - 202
  • [3] Non-wandering Sets for Dendrite Maps
    Sun, Taixiang
    He, Qiuli
    Liu, Jing
    Tao, Chunyan
    Xi, Hongjian
    QUALITATIVE THEORY OF DYNAMICAL SYSTEMS, 2015, 14 (01) : 101 - 108
  • [4] Non-wandering Sets for Dendrite Maps
    Taixiang Sun
    Qiuli He
    Jing Liu
    Chunyan Tao
    Hongjian Xi
    Qualitative Theory of Dynamical Systems, 2015, 14 : 101 - 108
  • [5] Genericity for Non-Wandering Surface Flows
    Yokoyama, Tomoo
    JOURNAL OF DYNAMICAL AND CONTROL SYSTEMS, 2017, 23 (02) : 197 - 212
  • [6] Statistical Mechanics of Surjective Cellular Automata
    Kari, Jarkko
    Taati, Siamak
    JOURNAL OF STATISTICAL PHYSICS, 2015, 160 (05) : 1198 - 1243
  • [7] Statistical Mechanics of Surjective Cellular Automata
    Jarkko Kari
    Siamak Taati
    Journal of Statistical Physics, 2015, 160 : 1198 - 1243
  • [8] VECTOR FIELDS WITH NO NON-WANDERING POINTS
    TAKENS, F
    WHITE, W
    AMERICAN JOURNAL OF MATHEMATICS, 1976, 98 (02) : 415 - 425
  • [9] Sharkovskii order for non-wandering points
    de Carvalho, Maria Pires
    Moreira, Fernando Jorge
    PORTUGALIAE MATHEMATICA, 2012, 69 (02) : 159 - 165
  • [10] Genericity for Non-Wandering Surface Flows
    Tomoo Yokoyama
    Journal of Dynamical and Control Systems, 2017, 23 : 197 - 212
12345