Cellular Automata on Group Sets
Abstrak
We introduce and study cellular automata whose cell spaces are left-homogeneous spaces. 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. For such automata and spaces, we prove, in particular, generalisations of topological and uniform variants of the Curtis-Hedlund-Lyndon theorem, of the Tarski-Følner theorem, and of the Garden-of-Eden theorem on the full shift and certain subshifts. Moreover, we introduce signal machines that can handle accumulations of events and using such machines we present a time-optimal quasi-solution of the firing mob synchronisation problem on finite and connected graphs.
Penulis (1)
Simon Wacker
Akses Cepat
- Tahun Terbit
- 2017
- Bahasa
- en
- Sumber Database
- arXiv
- Akses
- Open Access ✓