Search Results

Documents authored by Spicher, Antoine

Document
DOI: 10.4230/LIPIcs.MFCS.2022.49
Non-Determinism in Lindenmayer Systems and Global Transformations

Authors: Alexandre Fernandez, Luidnel Maignan, and Antoine Spicher

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
Global transformations provide a categorical framework for capturing synchronous rewriting systems, generalizing cellular automata to dynamical systems over dynamic spaces. Originally developed for addressing deterministic dynamical systems, the presented work raises the question of non-determinism. While a usual approach is to develop a general non-deterministic setting where deterministic systems can be retrieved as a specific case, we show here that by choosing the right parametrization, global transformations can already be used to handle non-determinism. Context-free Lindenmayer systems, already shown to be captured by global transformation in the deterministic case, are used to illustrate the approach. From this concrete example, the formal obstructions are exhibited, leading to a solution involving a 2-categorical monad and its associated Kleisli construction.
Cite as

Alexandre Fernandez, Luidnel Maignan, and Antoine Spicher. Non-Determinism in Lindenmayer Systems and Global Transformations. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 49:1-49:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fernandez_et_al:LIPIcs.MFCS.2022.49,
  author =	{Fernandez, Alexandre and Maignan, Luidnel and Spicher, Antoine},
  title =	{{Non-Determinism in Lindenmayer Systems and Global Transformations}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{49:1--49:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.49},
  URN =		{urn:nbn:de:0030-drops-168470},
  doi =		{10.4230/LIPIcs.MFCS.2022.49},
  annote =	{Keywords: Global Transformations, Non-deterministic Dynamical Systems, Lindenmayer Systems, Category Theory}
}
Document
DOI: 10.4230/OASIcs.AUTOMATA.2021.7
Cellular Automata and Kan Extensions

Authors: Alexandre Fernandez, Luidnel Maignan, and Antoine Spicher

Published in: OASIcs, Volume 90, 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)

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.
Cite as

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)

Copy BibTex To Clipboard

@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/entities/document/10.4230/OASIcs.AUTOMATA.2021.7},
  URN =		{urn:nbn:de:0030-drops-140160},
  doi =		{10.4230/OASIcs.AUTOMATA.2021.7},
  annote =	{Keywords: Cellular Automata, Kan Extension, Category Theory, Global Transformation}
}
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact