Functorial Analysis of Group-Alphabet Cellular Automata
Abstract
Let G be a group and let n∈ℕ. We consider one-dimensional cellular automata of length n over the alphabet G, with periodic boundary conditions and with local rules ϕ given by words. We construct a functor F from Grp, the category of groups (or any similar algebraic structure), to the category of pointed digraphs, and show its faithfulness. We introduce the image category 𝒞n,ϕ of state transition graphs of all such group-alphabet cellular automata, and show F is an equivalence onto this category. Consequently we investigate the translation of categorical structures in Grp in terms of automata, and give examples of how standard methods of homological algebra may now be applied to automata. Additionally, a graph-theoretical construction of the product in 𝒞n,ϕ is given, together with a formula for cycle lengths and multiplicities in this product. When G is abelian, further structural properties of state transition graphs follow, and we contrast these results with non-abelian counterexamples.
Related
- Generation by lazy and invertible cellular automata over the Klein four-group
- The Becker--Gottlieb transfer is not functorial: An example based on units of group rings
- Gardens of Eden and amenability on cellular automata
- Random Cellular Automata and deBruijn Graphs
- When do lazy and invertible cellular automata generate all cellular automata?
BibTeX
@misc{huard2026functorial,
title = {{Functorial Analysis of Group-Alphabet Cellular Automata}},
author = {François Huard and Nathan Dion Larivière},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.41013},
eprint = {2610.41013},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.41013},
}
RIS
TY - UNPB
TI - Functorial Analysis of Group-Alphabet Cellular Automata
AU - François Huard
AU - Nathan Dion Larivière
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.41013
UR - https://arxiv.org/abs/2610.41013
AB - Let G be a group and let n∈ℕ. We consider one-dimensional cellular automata of length n over the alphabet G, with periodic boundary conditions and with local rules ϕ given by words. We construct a functor F from Grp, the category of groups (or any similar algebraic structure), to the category of pointed digraphs, and show its faithfulness. We introduce the image category 𝒞_n,ϕ of state transition graphs of all such group-alphabet cellular automata, and show F is an equivalence onto this category. Consequently we investigate the translation of categorical structures in Grp in terms of automata, and give examples of how standard methods of homological algebra may now be applied to automata. Additionally, a graph-theoretical construction of the product in 𝒞_n,ϕ is given, together with a formula for cycle lengths and multiplicities in this product. When G is abelian, further structural properties of state transition graphs follow, and we contrast these results with non-abelian counterexamples.
ER -