{
  "id": "1610.00532",
  "version": "v1",
  "published": "2016-10-03T13:16:30.000Z",
  "updated": "2016-10-03T13:16:30.000Z",
  "title": "Cellular Automata and Finite Groups",
  "authors": [
    "Alonso Castillo-Ramirez",
    "Maximilien Gadouleau"
  ],
  "comment": "Submitted to Natural Computing, Special Issue Automata 2016. arXiv admin note: substantial text overlap with arXiv:1601.05694",
  "categories": [
    "math.GR",
    "cs.DM",
    "cs.FL"
  ],
  "abstract": "For a finite group $G$ and a finite set $A$, we study various algebraic aspects of cellular automata over the configuration space $A^G$. In this situation, the set $\\text{CA}(G;A)$ of all cellular automata over $A^G$ is a finite monoid whose basic algebraic properties had remained unknown. First, we investigate the structure of the group of units $\\text{ICA}(G;A)$ of $\\text{CA}(G;A)$. We obtain a decomposition of $\\text{ICA}(G;A)$ into a direct product of wreath products of groups that depends on the numbers $\\alpha_{[H]}$ of periodic configurations for conjugacy classes $[H]$ of subgroups of $G$. We show how the numbers $\\alpha_{[H]}$ may be computed using the M\\\"obius function of the subgroup lattice of $G$, and we use this to improve the lower bound recently found by Gao, Jackson and Seward on the number of aperiodic configurations of $A^G$. Furthermore, we study generating sets of $\\text{CA}(G;A)$; in particular, we prove that $\\text{CA}(G;A)$ cannot be generated by cellular automata with small memory set, and, when all subgroups of $G$ are normal, we determine the relative rank of $\\text{ICA}(G;A)$ on $\\text{CA}(G;A)$, i.e. the minimal size of a set $V \\subseteq \\text{CA}(G;A)$ such that $\\text{CA}(G;A) = \\langle \\text{ICA}(G;A) \\cup V \\rangle$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-10-03T13:16:30.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "68Q80",
      "05E18",
      "20M20"
    ],
    "keywords": [
      "cellular automata",
      "finite group",
      "small memory set",
      "basic algebraic properties",
      "finite set"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}