KIT | KIT-Bibliothek | Impressum | Datenschutz

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.


Volltext §
DOI: 10.5445/IR/1000070923
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Hochschulschrift
Publikationsjahr 2017
Sprache Englisch
Identifikator urn:nbn:de:swb:90-709236
KITopen-ID: 1000070923
Verlag Karlsruher Institut für Technologie (KIT)
Umfang XV, 424 S.
Art der Arbeit Dissertation
Fakultät Fakultät für Informatik (INFORMATIK)
Institut Institut für Theoretische Informatik (ITI)
Prüfungsdatum 08.06.2017
Schlagwörter 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
Referent/Betreuer Müller-Quade, J.
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page