License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.AUTOMATA.2021.7
URN: urn:nbn:de:0030-drops-140160
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14016/
Go to the corresponding OASIcs Volume Portal

Fernandez, Alexandre ; Maignan, Luidnel ; Spicher, Antoine

Cellular Automata and Kan Extensions

pdf-format:
OASIcs-AUTOMATA-2021-7.pdf (0.5 MB)

Abstract

In this paper, we formalize precisely the sense in which the application of a cellular automaton to partial configurations is a natural extension of its local transition function through the categorical notion of Kan extension. In fact, the two possible ways to do such an extension and the ingredients involved in their definition are related through Kan extensions in many ways. These relations provide additional links between computer science and category theory, and also give a new point of view on the famous Curtis-Hedlund theorem of cellular automata from the extended topological point of view provided by category theory. These links also allow to relatively easily generalize concepts pioneered by cellular automata to arbitrary kinds of possibly evolving spaces. No prior knowledge of category theory is assumed.

BibTeX - Entry

@InProceedings{fernandez_et_al:OASIcs.AUTOMATA.2021.7,
  author =	{Fernandez, Alexandre and Maignan, Luidnel and Spicher, Antoine},
  title =	{{Cellular Automata and Kan Extensions}},
  booktitle =	{27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)},
  pages =	{7:1--7:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-189-4},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{90},
  editor =	{Castillo-Ramirez, Alonso and Guillon, Pierre and Perrot, K\'{e}vin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14016},
  URN =		{urn:nbn:de:0030-drops-140160},
  doi =		{10.4230/OASIcs.AUTOMATA.2021.7},
  annote =	{Keywords: Cellular Automata, Kan Extension, Category Theory, Global Transformation}
}

Keywords: Cellular Automata, Kan Extension, Category Theory, Global Transformation
Collection: 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)
Issue Date: 2021
Date of publication: 28.06.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI