Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



The dynamics of expansive invertible onesided cellular automata

Author: Masakazu Nasu
Journal: Trans. Amer. Math. Soc. 354 (2002), 4067-4084
MSC (2000): Primary 37B15; Secondary 37B10, 54H20
Published electronically: June 4, 2002
MathSciNet review: 1926865
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Using textile systems, we prove the conjecture of Boyle and Maass that the dynamical system defined by an expansive invertible onesided cellular automaton is topologically conjugate to a topological Markov shift. We also study expansive leftmost-permutive onesided cellular automata and bipermutive endomorphisms of mixing topological Markov shifts.

References [Enhancements On Off] (What's this?)

  • [AH] N. Aoki and K. Hiraide, Topological Theory of Dynamical Systems, Recent Advances, North-Holland, Amsterdam, 1994. MR 95m:58095
  • [BFF] M. Boyle, D. Fiebig and U. Fiebig, A dimension group for local homeomorphisms and endomorphisms of onesided shifts of finite type, J. Reine Angew. Math. 487 (1997), 27-59. MR 98i:54020
  • [BL] M. Boyle and D. Lind, Expansive subdynamics, Trans. Amer. Math. Soc. 349 (1997), 55-102. MR 97d:58115
  • [BM] M. Boyle and A. Maass, Expansive invertible onesided cellular automata, J. Math. Soc. Japan 52 (2000), 725-740; corrigendum, preprint. MR 2001g:37011
  • [C] E. M. Coven, Topological entropy of block maps, Proc. Amer. Math. Soc. 78 (1980), 590-594. MR 80m:54055
  • [F] R. Fischer, Sofic systems and graphs, Monatsh. Math. 80 (1975), 179-186. MR 53:11018
  • [Ki] B. Kitchens, Symbolic Dynamics, One-sided, Two-sided and Countable State Markov Chains, Springer-Verlag, 1998. MR 98k:58079
  • [Ko] T. Kobayashi, Computer experiments which investigate the properties of onesided cellular automata (in Japanese), Master's Thesis, Mie University, Tsu (1995).
  • [Ku] P. K'urka, Languages, equicontinuity and attractors in cellular automata, Ergodic Theory Dynam. Systems 17 (1997), 417-433. MR 98b:58092
  • [LM] D. Lind and B. Marcus, Symbolic Dynamics and Coding, Cambridge University, 1995. MR 97a:58050
  • [N1] M. Nasu, Constant-to-one and onto global maps of homomorphisms between strongly connected graphs, Ergodic Theory Dynam. Systems 3 (1983), 387-413. MR 85m:58162
  • [N2] -, Textile systems for endomorphisms and automorphisms of the shift, Mem. Amer. Math. Soc. 546 (1995). MR 95i:54051
  • [N3] -, Maps in symbolic dynamics, in Lecture Notes of The Tenth KAIST Mathematics Workshop 1995, ed. G. H. Choe, Korea Advanced Institute of Science and Technology, Mathematics Research Center, Taejon, 1996.
  • [N4] -, Endomorphisms of expansive systems on compact metric spaces and the pseudo-orbit tracing property, Trans. Amer. Math. Soc. 352 (2000), 4731-4757. MR 2001b:54049
  • [SA] M. A. Shereshevsky and V. S. Afraimovich, Bipermutative cellular automata are topologically conjugate to the one-sided Bernoulli shift, Random Comput. Dynam. 1 (1992), 91-98. MR 93i:58082
  • [U] M. Uchida, Generation of the leftmost-permutive cellular automata whose global maps are bijective (in Japanese), Master's Thesis, Mie University, Tsu (1994).

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 37B15, 37B10, 54H20

Retrieve articles in all journals with MSC (2000): 37B15, 37B10, 54H20

Additional Information

Masakazu Nasu
Affiliation: Graduate School of Engineering, Hiroshima University, Higashi-Hiroshima 739-8527, Japan

Keywords: Cellular automata, topological Markov shifts, expansive, symbolic dynamics, textile systems
Received by editor(s): October 12, 2001
Received by editor(s) in revised form: March 28, 2002
Published electronically: June 4, 2002
Additional Notes: This research was partially supported by Grant-in-Aid for Scientific Research (No. 11674021), Ministry of Education, Culture, Sports, Science and Technology, Japan
Article copyright: © Copyright 2002 American Mathematical Society

American Mathematical Society