KIT | KIT-Bibliothek | Impressum | Datenschutz
Open Access Logo
DOI: 10.5445/IR/1000070923

Cellular Automata on Group Sets

Wacker, Simon

Abstract (englisch):
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 arbitrary singularities and using such machines we present a time-optimal quasi-solution of the firing mob synchronisation problem on finite and connected graphs.

Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Hochschulschrift
Jahr 2017
Sprache Englisch
Identifikator URN: urn:nbn:de:swb:90-709236
KITopen-ID: 1000070923
Verlag Karlsruhe
Umfang XV, 424 S.
Abschlussart Dissertation
Fakultät Fakultät für Informatik (INFORMATIK)
Institut Institut für Theoretische Informatik (ITI)
Prüfungsdatum 08.06.2017
Referent/Betreuer Prof. J. Müller-Quade
Schlagworte Cellular Automaton, Signals Machine, Curtis-Hedlund-Lyndon Theorem, Tarski-Følner Theorem, Garden-of-Eden Theorem, Shift Spaces, Moore-Myhill Property, Firing squad Synchronisation Problem, Dissertation
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft KITopen Landing Page