{
  "id": "1706.08429",
  "version": "v1",
  "published": "2017-06-26T15:11:51.000Z",
  "updated": "2017-06-26T15:11:51.000Z",
  "title": "Cellular Automata on Group Sets",
  "authors": [
    "Simon Wacker"
  ],
  "comment": "This is my doctoral dissertation. It consists of extended versions of the articles arXiv:1603.07271 [math.GR], arXiv:1603.06460 [math.GR], arXiv:1603.07272 [math.GR], arXiv:1701.02108 [math.GR], arXiv:1706.05827 [math.GR], and arXiv:1706.05893 [cs.FL]",
  "doi": "10.5445/IR/1000070923",
  "categories": [
    "math.GR",
    "cs.FL"
  ],
  "abstract": "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{\\o}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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-06-26T15:11:51.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "group sets",
      "study cellular automata",
      "firing mob synchronisation problem",
      "left-homogeneous spaces",
      "uniform tilings"
    ],
    "tags": [
      "dissertation",
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}