Algorightms for inferring context-sensitive L-systems

Ian McQuillan1, Jason Bernard1, and Przemyslaw Prusinkiewicz2.

1Department of Computer Science, University of Saskatchewan
2Department of Computer Science, University of Calgary

Abstract

Lindenmayer systems (L-systems) are parallel string rewriting systems (grammars). By attaching a graphical interpretation to the symbols in the derived strings, they can be applied to create simulations of temporal processes, and have been especially successful in the modeling of plants. With the objective of automatically inferring L-system models in mind, here we study the inductive inference problem: the inference of models from observed strings. Exact algorithms are given for inferring L-systems that can generate input strings for both deterministic context-free and deterministic context-sensitive L-systems. The algorithms run in polynomial time assuming a fixed number of alphabet symbols and fixed context size. Furthermore, if a specific matrix calculated from the input words is invertible, then a context-sensitive L-system can be automatically created (if it exists) in polynomial time without assuming any fixed parameters.

Reference

Ian McQuillan, Jason Bernard, and Przemyslaw Prusinkiewicz. Algorithms for Inferring Context-Sensitive L-Systems. International Conference on Unconventional Computation and Natural Computation. Springer, Cham, 2018.

Download PDF here (420 Kb).