License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2022.49
URN: urn:nbn:de:0030-drops-168470
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16847/
Go to the corresponding LIPIcs Volume Portal

Fernandez, Alexandre ; Maignan, Luidnel ; Spicher, Antoine

Non-Determinism in Lindenmayer Systems and Global Transformations

pdf-format:
LIPIcs-MFCS-2022-49.pdf (0.6 MB)

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.

BibTeX - Entry

@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/opus/volltexte/2022/16847},
  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}
}

Keywords: Global Transformations, Non-deterministic Dynamical Systems, Lindenmayer Systems, Category Theory
Collection: 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Issue Date: 2022
Date of publication: 22.08.2022

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