Document Open Access Logo

Non-Determinism in Lindenmayer Systems and Global Transformations

Authors Alexandre Fernandez, Luidnel Maignan, Antoine Spicher

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2022.49.pdf
  • Filesize: 0.63 MB
  • 13 pages

Document Identifiers

Author Details

Alexandre Fernandez
  • Univ Paris Est Creteil, LACL, 94000, Creteil, France
Luidnel Maignan
  • Univ Paris Est Creteil, LACL, 94000, Creteil, France
  • Université Paris-Saclay, Inria, CNRS, ENS Paris-Saclay, LMF, 91190, Gif-sur-Yvette, France
Antoine Spicher
  • Univ Paris Est Creteil, LACL, 94000, Creteil, France

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.MFCS.2022.49

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parallel computing models
  • Theory of computation → Concurrency
  • Mathematics of computing → Discrete mathematics
  • Computing methodologies → Modeling and simulation
Keywords
  • Global Transformations
  • Non-deterministic Dynamical Systems
  • Lindenmayer Systems
  • Category Theory

Metrics

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

References

  1. Enrico Biermann, Hartmut Ehrig, Claudia Ermel, Ulrike Golas, and Gabriele Taentzer. Parallel independence of amalgamated graph transformations applied to model transformation. In Graph transformations and model-driven engineering, pages 121-140. Springer, 2010. Google Scholar
  2. Paul Boehm, Harald-Reto Fonio, and Annegret Habel. Amalgamation of graph transformations: a synchronization mechanism. Journal of Computer and System Sciences, 34(2-3):377-408, 1987. Google Scholar
  3. Francis Borceux and George Janelidze. Galois theories, volume 72. Cambridge University Press, 2001. Google Scholar
  4. 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.
  5. Alexandre Fernandez, Luidnel Maignan, and Antoine Spicher. Accretive computation of global transformations. In International Conference on Relational and Algebraic Methods in Computer Science, pages 159-175. Springer, 2021. Google Scholar
  6. Alexandre Fernandez, Luidnel Maignan, and Antoine Spicher. The bicategory of open functors, 2021. URL: http://arxiv.org/abs/2102.08051.
  7. Alexandre Fernandez, Luidnel Maignan, and Antoine Spicher. Cellular automata and kan extensions. arXiv preprint, 2021. URL: http://arxiv.org/abs/2102.12156.
  8. Marcelo Fiore, Nicola Gambino, Martin Hyland, and Glynn Winskel. Relative pseudomonads, kleisli bicategories, and substitution monoidal structures. Selecta Mathematica, 24(3):2791-2830, 2018. Google Scholar
  9. Hongde Hu and Walter Tholen. Limits in free coproduct completions. Journal of Pure and Applied Algebra, 105(3):277-291, 1995. URL: https://doi.org/10.1016/0022-4049(94)00153-7.
  10. Karel Klouda and Štěpán Starosta. Characterization of circular d0l-systems. Theoretical Computer Science, 790:131-137, 2019. URL: https://doi.org/10.1016/j.tcs.2019.04.021.
  11. Daniel Lehmann. Categories for fixpoint semantics. PhD thesis, University of Warwick, 1976. Google Scholar
  12. 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.
  13. Grzegorz Rozenberg and Arto Salomaa. The mathematical theory of L systems, volume 90. Academic press, 1980. Google Scholar
  14. Karthik Yegnesh. The fundamental infinity-groupoid of a parametrized family. arXiv preprint, 2017. URL: http://arxiv.org/abs/1701.02250.
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