Cellular Automata and Kan Extensions

Authors Alexandre Fernandez, Luidnel Maignan, Antoine Spicher



PDF
Thumbnail PDF

File

OASIcs.AUTOMATA.2021.7.pdf
  • Filesize: 499 kB
  • 12 pages

Document Identifiers

Author Details

Alexandre Fernandez
  • Université Paris Est Creteil, LACL, F-94010 Creteil, France
Luidnel Maignan
  • Université Paris Est Creteil, LACL, F-94010 Creteil, France
Antoine Spicher
  • Université Paris Est Creteil, LACL, F-94010 Creteil, France

Cite AsGet BibTex

Alexandre Fernandez, Luidnel Maignan, and Antoine Spicher. Cellular Automata and Kan Extensions. In 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021). Open Access Series in Informatics (OASIcs), Volume 90, pp. 7:1-7:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/OASIcs.AUTOMATA.2021.7

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Rewrite systems
  • Theory of computation → Models of computation
Keywords
  • Cellular Automata
  • Kan Extension
  • Category Theory
  • Global Transformation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Tullio Ceccherini-Silberstein and Michel Coornaert. Cellular automata and groups. Springer Science & Business Media, 2010. Google Scholar
  2. Alexandre Fernandez, Luidnel Maignan, and Antoine Spicher. Lindenmayer systems and global transformations. In Ian McQuillan and Shinnosuke Seki, editors, Unconventional Computation and Natural Computation - 18th International Conference, UCNC 2019, Tokyo, Japan, June 3-7, 2019, Proceedings, volume 11493 of Lecture Notes in Computer Science, pages 65-78. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-19311-9_7.
  3. Gustav A Hedlund. Endomorphisms and automorphisms of the shift dynamical system. Mathematical systems theory, 3(4):320-375, 1969. Google Scholar
  4. S. MacLane. Categories for the Working Mathematician. Graduate Texts in Mathematics. Springer New York, 2013. Google Scholar
  5. Luidnel Maignan and Antoine Spicher. Global graph transformations. In Detlef Plump, editor, Proceedings of the 6th International Workshop on Graph Computation Models co-located with the 8th International Conference on Graph Transformation (ICGT 2015) part of the Software Technologies: Applications and Foundations (STAF 2015) federation of conferences, L'Aquila, Italy, July 20, 2015, volume 1403 of CEUR Workshop Proceedings, pages 34-49. CEUR-WS.org, 2015. URL: http://ceur-ws.org/Vol-1403/paper4.pdf.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail