Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-15T11:26:33.582Z Has data issue: false hasContentIssue false
  • English
  • Français

Induction and restriction of cellular automata

Published online by Cambridge University Press:  01 April 2009

TULLIO CECCHERINI-SILBERSTEIN and
MICHEL COORNAERT
TULLIO CECCHERINI-SILBERSTEIN
Affiliation:
Dipartimento di Ingegneria, Università del Sannio, C.so Garibaldi 107, 82100 Benevento, Italy (email: tceccher@mat.uniroma1.it)
MICHEL COORNAERT
Affiliation:
Institut de Recherche Mathématique Avancée, Université Louis Pasteur et CNRS, 7 rue René Descartes, 67084 Strasbourg Cedex, France (email: coornaert@math.u-strasbg.fr)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We analyze in detail the notions of induction and restriction for cellular automata. As a by-product we extend a few classical and recent theorems on cellular automata to uncountable groups.

Information

Type
Research Article
Information
Ergodic Theory and Dynamical Systems , Volume 29 , Issue 2 , April 2009, pp. 371 - 380
Copyright
Copyright © Cambridge University Press 2008

References

[1]Bartholdi, L.. A converse to Moore’s and Hedlund’s theorems on cellular automata. J. Eur. Math. Soc. (JEMS) to appear.Google Scholar
[2]Ceccherini-Silberstein, T. and Coornaert, M.. The Garden of Eden theorem for linear cellular automata. Ergod. Th. & Dynam. Sys. 26 (2006), 53–68.Google Scholar
[3]Ceccherini-Silberstein, T. and Coornaert, M.. Injective linear cellular automata and sofic groups. Israel J. Math. 161 (2007), 1–15.CrossRefGoogle Scholar
[4]Ceccherini-Silberstein, T. and Coornaert, M.. Amenability and linear cellular automata over semisimple modules of finite length. Comm. Algebra 36 (2008), 1320–1335.CrossRefGoogle Scholar
[5]Ceccherini-Silberstein, T. and Coornaert, M.. A generalization of the Curtis–Hedlund theorem. Theoret. Comput. Sci. 400 (2008), 225–229.CrossRefGoogle Scholar
[6]Ceccherini-Silberstein, T., Grigorchuk, R. I. and de la Harpe, P.. Amenability and paradoxical decompositions for pseudogroups and for discrete metric spaces. Proc. Steklov Inst. Math. 224 (1999), 57–97.Google Scholar
[7]Ceccherini-Silberstein, T. G., Machì, A. and Scarabotti, F.. Amenable groups and cellular automata. Ann. Inst. Fourier (Grenoble) 49 (1999), 673–685.CrossRefGoogle Scholar
[8]Glebsky, L. Yu. and Gordon, E. I.. On surjunctivity of the transition functions of cellular automata on groups. Taiwanese J. Math. 9(3) (2005), 511–520.Google Scholar
[9]Gottschalk, W.. Some general dynamical systems. Recent Advances in Topological Dynamics (Lecture Notes in Mathematics, 318). Springer, Berlin, pp. 120–125.Google Scholar
[10]Gottschalk, W. H. and Hedlund, G. A.. Topological Dynamics (American Mathematical Society Colloquium Publications, 36). American Mathematical Society, Providence, RI, 1955.Google Scholar
[11]Gromov, M.. Endomorphisms of symbolic algebraic varieties. J. Eur. Math. Soc. (JEMS) 1 (1999), 109–197.CrossRefGoogle Scholar
[12]Machì, A. and Mignosi, F.. Garden of Eden configurations for cellular automata on Cayley graphs of groups. SIAM J. Discrete Math. 6 (1993), 44–56.CrossRefGoogle Scholar
[13]Moore, E. F.. Machine Models of Self-reproduction (Proceedings of Symposia in Applied Mathematics, 14). American Mathematical Society, Providence, RI, 1963, pp. 17–34.Google Scholar
[14]Muller, D. E.. Class Notes. University of Illinois, Urbana IL, 1976.Google Scholar
[15]Myhill, J.. The converse of Moore’s Garden of Eden theorem. Proc. Amer. Math. Soc. 14 (1963), 685–686.Google Scholar
[16]Weiss, B.. Sofic groups and dynamical systems (Ergodic theory and harmonic analysis, Mumbai, 1999). Sankhya Ser. A. 62 (2000), 350–359.Google Scholar