Acta mathematica scientia, Series B >
TOPOLOGICAL ENTROPY OF PERIODIC COVEN CELLULAR AUTOMATA
Received date: 2014-11-20
Revised date: 2015-06-02
Online published: 2016-04-25
Supported by
The first author is supported by the Fundamental Research Funds for the Central Universities (2012201020204), and the second author is supported by NSFC (11171128, 11271148).
We investigate topological entropy of periodic Coven cellular automatas; that is, the maps FB:{0, 1}Z→{0, 1}Z defined by FB(x)i=xi+
(xi+j+bj) (mod 2), where B=b1b2…br∈{0, 1}r(r≥2), is a periodic word. In particular, we prove that if the minimal period of B is greater than r/2, the topological entropy is log 2.
Key words： Cellular automata; periodic word; topological entropy
Weibin LIU , Jihua MA . TOPOLOGICAL ENTROPY OF PERIODIC COVEN CELLULAR AUTOMATA[J]. Acta mathematica scientia, Series B, 2016 , 36(2) : 579 -592 . DOI: 10.1016/S0252-9602(16)30022-4
[1] Adler R, Konheim A, McAndrew M. Topological entropy. Trans Amer Math Soc, 1965, 114:309-319
[2] Blanchard F, Glasner E, Kolyada S. On Li-Yorke pairs. J Reine Angew Math, 2002, 547:51-68
[3] Blanchard F, Maass A. Dynamical behaviour of Coven's aperiodic cellular automata. Theoret Comput Sci, 1996, 163:291-302
[4] Blanchard F, Tisseur P. Some properties of cellular automata with equicontinous points. Ann Inst Henri Poincaré, 2000, 36:569-582
[5] Coven E M. Topological entropy of block maps. Proc Amer Math Soc, 1980, 78:590-594
[6] Coven E M, Hedlund G A. Periods of some nonlinear shift registers. J Combina Theory, 1979, 27A:186-197
[7] Codenotti B, Margara L. Transitive cellular automata are sensitive. Amer Math Monthly, 1996, 103:58-62
[8] Delorme M, Formenti E, Mazoyer J. Open problem on cellular automata. Technical report RR-2000-25. É cole Normale Supérieure de Lyon, 2000
[9] Denker M, Grillenberger C, Sigmund K. Ergodic Theory on Compact Space. Berlin:Springer-Verlag, 1976
[10] D'amico M, Manzhi G, Margara L. On computing the entropy of cellular automata. Theoret Comput Sci, 2003, 290:1629-1646
[11] Fine N J, Wilf H S. Uniqueness theorem for periodic functions. Proc Amer Math Soc, 1965, 16:109-114
[12] Goodman T N T. Relating topological entropy and measure entropy. Bull London Math Soc, 1971, 3:176-180
[13] Gardner M. Mathematical Games-The fantastic combinations of John Conway's new solitaire game "life". Sci Am, 1970, 223:120-123
[14] Guibas L J, Odlyzko A M. Periods in strings. J Combin Theory, 1981, 30A:19-42
[15] Hedlund G A. Endomorphisms and automorphisms of the shift dynamical system. Math Syst Theory, 1969, 3:320-375
[16] Hurd L P, Kari J, Culik K. The topological entropy of cellular automata is uncomputable. Ergodic Theory Dynam Systems, 1992, 12:255-265
[17] Kitchens B. Symbolic Dynamical, One-sided, Two-sided and Countable State Markov Shifts. Berlin:Springer, 1998
[18] K?rka P. Topological and Symbolic Dynamics. Cours Spécialisés-Collection SMF, 2003
[19] K?rka P. Languages, equicontinuity and attractors in cellular automata. Ergodic Theory Dynam Systems, 1997, 17(2):417-433
[20] Lothaire M. Algebraic Combinatorics on Words. Cambridge:Cambridge University Press, 2002
[21] Lind D, Marcus B. An Introduction to Symbolic Dynamics and Coding. Cambridge:Cambridge University Press, 1995
[22] Moothathu T K S. Surjective cellular automata with zero entropy are almost one-to-one. Chaos Solitons Fractals, 2011, 44:415-417
[23] von Neumann J. Theory of Self-reproducing Automata. Urbana:University of Illinios, 1966
[24] Tisseur P. Cellular automata and Lyapunov exponents. Nonlinearity, 2000, 13:1547-1560
[25] Walters P. An Introduce to Ergodic Theory. New York:Springer-Verlag, 1982
[26] Wolfram S. Computation theory of cellular automata. Comm Math Phys, 1984, 96:15-57
[27] Wolfram S. Theory and Application of Cellular Automata. Singapore:World Scientific, 1986
/
| 〈 |
|
〉 |