Top

Natural Computing

Published in:

27-01-2023

Cellular automata and Kan extensions

Authors: Alexandre Fernandez, Luidnel Maignan, Antoine Spicher

Published in: Natural Computing | Issue 3/2023

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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 for the most part.

previous article Enumeration of maximal cycles generated by orthogonal cellular automata

next article Cellular automata and substitutions in topological spaces defined via edit distances

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

We chose the collection of objects and arrows to be sets. They are classes in usual definitions.

Note that one can only compose pairs of arrows where the first arrow starts where the second arrow ends, for instance \(g \circ f\) is defined for \(g : y \rightarrow z\) and \(f : x \rightarrow y\). This means that associativity, left neutrality and right neutrality only holds when they are defined.

Arrighi P, Dowek G (2012) Causal graph dynamics. In: Artur C, Kurt M, Andrew MP, Roger W (eds) Automata, languages, and programming - 39th international colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part II, volume 7392 of lecture notes in computer science. Springer, pp 54–66. Springer

Banâtre J-P, Fradet P, Le MD (2000) Gamma and the chemical reaction model: fifteen years after. In: Workshop on membrane computing. Springer, pp 17–44

Berry Gérard, Boudol G (1992) The chemical abstract machine. Theor Comput Sci 96(1):217–248MathSciNetCrossRefMATH

Ceccherini-Silberstein T, Coornaert M (2010) Cellular automata and groups. Springer Science & Business Media

Fernandez A, Maignan L, Spicher A (2019) Lindenmayer systems and global transformations. In: Ian M and Shinnosuke S (eds) 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. Springer, pp 65–78

Fernandez A, Maignan L, Spicher A (2021) Accretive computation of global transformations. In: International conference on relational and algebraic methods in computer science. Springer, pp 159–175

Hedlund GA (1969) Endomorphisms and automorphisms of the shift dynamical system. Math Syst Theor 3(4):320–375MathSciNetCrossRefMATH

MacLane S (2013) Categories for the working mathematician. In: Graduate texts in mathematics. Springer, New York

Maignan L, Spicher A (2015) Global graph transformations. In: Detlef P (eds) 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, pp 34–49. CEUR-WS.org

Păun Gheorghe (2001) From cells to computers: computing with membranes (p systems). Biosystems 59(3):139–158CrossRef

Rozenberg G, Salomaa A (2012) Lindenmayer systems: impacts on theoretical computer science, computer graphics, and developmental biology. Springer Science & Business Media

Spicher A, Giavitto J-L (2017) Interaction-based programming in mgs. In: Advances in unconventional computing. Springer, pp 305–342

Title: Cellular automata and Kan extensions
Authors: Alexandre Fernandez
Luidnel Maignan
Antoine Spicher
Publication date: 27-01-2023
Publisher: Springer Netherlands
Published in: Natural Computing / Issue 3/2023
Print ISSN: 1567-7818
Electronic ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-022-09931-0

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 3/2023

Programmable single-stranded architectures for computing

Cellular automata and substitutions in topological spaces defined via edit distances

Complexity of limit cycles with block-sequential update schedules in conjunctive networks

Gauge-invariance in cellular automata

Preface

Linear cuts in Boolean networks

Premium Partner