Top

Natural Computing

Published in:

04-10-2017

Cellular automata on group sets and the uniform Curtis–Hedlund–Lyndon theorem

Author: Simon Wacker

Published in: Natural Computing | Issue 3/2019

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We introduce cellular automata whose cell spaces are left-homogeneous spaces, show that their global transition functions are closed under composition, prove a uniform as well as a topological variant of the Curtis–Hedlund–Lyndon theorem, and deduce that such an automaton is invertible if and only if its global transition function is bijective. Examples of left-homogeneous spaces are spheres, Euclidean spaces, as well as hyperbolic spaces acted on by isometries; uniform tilings acted on by symmetries; vertex-transitive graphs, in particular, Cayley graphs, acted on by automorphisms; groups acting on themselves by multiplication; and integer lattices acted on by translations.

previous article Cellular automata and finite groups

next article Waiting for the rapture: What can we do with computers to (hopefully) witness the emergence of life?

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Ceccherini-Silberstein T, Coornaert M (2008) A generalization of the Curtis–Hedlund theorem. Theor Comput Sci 400(1–3):225–229MathSciNetCrossRefMATH

Ceccherini-Silberstein T, Coornaert M (2010) Cellular automata and groups. Springer monographs in mathematics. Springer, BerlinCrossRefMATH

Gonçalves D, Sobottka M, Starling C (2016) Sliding block codes between shift spaces over infinite alphabets. Math Nachr 289(17–18):2178–2191MathSciNetCrossRefMATH

Gorbatsevich VV, Onishchik AL, Kozlowski T, Vinberg EB (2013) Lie groups and Lie algebras I: Foundations of Lie theory Lie transformation groups. Encyclopaedia of mathematical sciences. Springer, Berlin

Hedlund GA (1969) Endomorphisms and automorphisms of the shift dynamical system. Math Syst Theory 3(4):320–375MathSciNetCrossRefMATH

Kassel F (2012) Deformation of proper actions on reductive homogeneous spaces. Math Ann 353(2):599–632MathSciNetCrossRefMATH

Lee JM (2013) Introduction to smooth manifolds. Graduate texts in mathematics. Springer, Berlin

Moriceau S (2011) Cellular automata on a \(G\)-set. J Cell Autom 6(6):461–486MathSciNet

Ott W, Tomforde M, Willis PN (2014) One-sided shift spaces over infinite alphabets. N Y J Math Monogr 5:54pp

Sobottka M, Gonçalves D (2017) A note on the definition of sliding block codes and the Curtis–Hedlund–Lyndon theorem. J Cell Autom 12(3–4):209–215MathSciNet

Wacker S (2016) The Garden of Eden theorem for cellular automata on group sets. In: Cellular automata, pp 66–78. arXiv:1603.07272 [math.GR]

Wacker S (2017) Right amenable left group sets and the Tarski–Følner theorem. In: International journal of group theory. arXiv:1603.06460 [math.GR] (to be published)

Willard S (2012) General topology. Dover books on mathematics. Dover, New York

Title: Cellular automata on group sets and the uniform Curtis–Hedlund–Lyndon theorem
Author: Simon Wacker
Publication date: 04-10-2017
Publisher: Springer Netherlands
Published in: Natural Computing / Issue 3/2019
Print ISSN: 1567-7818
Electronic ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-017-9645-y

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 3/2019

Variants of P systems with activation and blocking of rules

A membrane computing framework for self-reconfigurable robots

A quantum-inspired vortex search algorithm with application to function optimization

Preface

Waiting for the rapture: What can we do with computers to (hopefully) witness the emergence of life?

Perturbations and phase transitions in swarm optimization algorithms

Premium Partner