Editing L-system (section)

== L-system Construction and Inference ==

=== Manual L-System Construction ===
Historically, the construction of L-systems relied heavily on manual efforts by experts,<ref>Dinnus Frijters and Aristid Lindenmayer. A model for the growth and owering of Aster novae-angliae on the basis of table < 10 > L-systems. In L systems, pages 2452. Springer, 1974.</ref><ref name=":0">Prusinkiewicz, P., & Lindenmayer, A. (2012). ''The algorithmic beauty of plants''. Springer Science & Business Media.</ref><ref name=":1">T. Nishida, K0L-system simulating almost but not exactly the same development-case of Japanese Cypress, Memoirs of the Faculty of Science, Kyoto University, Series B 8 (1) (1980) 97122.</ref> requiring detailed measurements, domain knowledge, and significant time investment. The process often involved analyzing biological structures and encoding their developmental rules into L-systems, symbol by symbol. This labor-intensive method made creating accurate models for complex processes both tedious and error-prone.

A notable example is Nishida's <ref name=":1" /> work on Japanese Cypress trees, where he manually segmented branches from a series of images and identified 42 distinct growth mechanisms to construct a stochastic L-system. Despite the significant effort involved, the resulting system provided only an approximation of the tree's growth, illustrating the challenges of manually encoding such detailed biological processes. This arduous task was described as "tedious and intricate," underscoring the limitations of manual approaches.

The challenges of manual L-system construction are also well-documented in The Algorithmic Beauty of Plants <ref name=":0" /> by Przemyslaw Prusinkiewicz and Aristid Lindenmayerd. The book demonstrates how L-systems can elegantly model plant growth and fractal patterns, but the examples often required expert intervention to define the necessary rules.

Manual construction was further constrained by the need for domain-specific expertise, as seen in other applications of L-systems beyond biology, such as architectural design and urban modeling.<ref>Pascal Muller, Peter Wonka, Simon Haegler, Andreas Ulmer, and Luc Van Gool. Procedural modeling of buildings. ACM Transactions On Graphics, 25(3):614623, 2006.</ref> In these fields, creating an accurate L-system required not only an understanding of the L-system formalism but also extensive knowledge of the domain being modeled.

=== L-system Inference ===

The idea of automating L-system inference emerged to address the inefficiencies of manual methods, which often required extensive expertise, measurements, and trial-and-error processes. This automation aimed to enable the inference of L-systems directly from observational data, eliminating the need for manual encoding of rules.

Initial algorithms primarily targeted deterministic context-free L-systems (D0L-systems), which are among the simplest types of L-systems. These early efforts demonstrated the feasibility of automatic inference but were severely limited in scope, typically handling only systems with small alphabets and simple rewriting rules.<ref>Bian Runqiang, Phoebe Chen, Kevin Burrage, Jim Hanan, Peter Room, and John Belward. Derivation of L-system models from measurements of biological branching structures using genetic algorithms. In Proceedings of the International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems, pages 514524. Springer, 2002.</ref><ref name=":2">Ryohei Nakano. Emergent induction of deterministic context-free L-system grammar. In Innovations in Bio-inspired Computing and Applications, pages 7584. Springer International Publishing, 2014.</ref><ref>P. G. Doucet. The syntactic inference problem for D0L-sequences. L Systems, pages 146161, 1974</ref><ref name=":3">Roger Curry. On the evolution of parametric L-systems. Technical report, University of Calgary, 2000.</ref> For instance, Nakano's <ref name=":2" /> work highlighted the challenges of inferring L-systems with larger alphabets and more complex structures, describing the task as "immensely complicated".

=== Manual and Semi-Automated Tools ===
Early tools for L-system inference were often designed to assist experts rather than replace them. For example, systems that presented a population of potential L-systems to the user, allowing them to select aesthetically pleasing or plausible options, reduced some of the manual burden.<ref name=":3" /><ref name=":4">Fabricio Anastacio, Przemyslaw Prusinkiewicz, and Mario Costa Sousa. Sketch-based parameterization of L-systems using illustration-inspired construction lines and depth modulation. Computers & Graphics, 33(4):440451, 2009.</ref> However, these tools relied heavily on human judgment and did not fully automate the inference process.

=== Domain-Specific Inference Approaches ===
Some early algorithms were tightly integrated into specific research domains mainly plant modeling.<ref name=":4" /> These approaches utilized domain knowledge to constrain the search space and achieve better results. However, their reliance on predefined domain-specific rules limited their generalizability and applicability to other areas.

=== Generalized Inference Algorithms ===
Attempts to create generalized algorithms for L-system inference began with deterministic context-free systems. Researchers aimed to infer L-systems from data alone, such as sequences of strings or temporal data from images, without relying on domain-specific knowledge. These algorithms encountered significant challenges,<ref>Colin De La Higuera. A bibliographical study of grammatical inference. Pattern Recognition, 38(9):1332 1348, 2005.</ref><ref>Kari, L., Rozenberg, G., & Salomaa, A. (1997). ''L systems'' (pp. 253-328). Springer Berlin Heidelberg.</ref> including:

* The exponential growth of the search space with increasing alphabet size and rule complexity. 

* Dealing with imperfect or noisy data, which introduced errors in the inferred systems.

* Limitations in computational efficiency, as exhaustive search methods became intractable for all but the simplest cases.

Bernard's PhD dissertation,<ref>Bernard, J. (2020). ''Inferring Different Types of Lindenmayer Systems Using Artificial Intelligence'' (Doctoral dissertation, University of Saskatchewan).</ref> supervised by Dr. Ian McQuillan at the University of Saskatchewan, represents a significant advancement in L-system inference, introducing the Plant Model Inference Tools (PMIT) suite. Despite the name, this tool is problem agnostic, and is so-named due to the source of the original funding from the P2IRC project. These tools address the challenges of inferring deterministic, stochastic, and parametric L-systems:

'''Deterministic Context-Free L-Systems (D0L):'''

The PMIT-D0L tool improved the state-of-the-art by enabling the inference of L-systems with up to 31 symbols, compared to previous algorithms that managed only two. This was achieved through novel encoding techniques and search-space reduction methods.

'''Deterministic Context-Sensitive L-Systems (D(j,k)L):'''

The PMIT-DCSL tool further improved the inference of deterministic L-systems by demonstrating that the techniques worked in the context-sensitive case with little modification. This tool also presented further improvements allowing for the inference of deterministic L-systems with up to hundreds of symbols. Furthermore, this work and McQuillan's <ref>McQuillan, I., Bernard, J., & Prusinkiewicz, P. (2018). Algorithms for inferring context-sensitive L-systems. In ''Unconventional Computation and Natural Computation: 17th International Conference, UCNC 2018, Fontainebleau, France, June 25-29, 2018, Proceedings 17'' (pp. 117-130). Springer International Publishing.</ref> theoretical paper proves the complexity of context-sensitive L-systems inference. In an unpublished work, Bernard claims to show that context-sensitivity never changes the fundamental nature of the inference problem regardless of the selection rule. That is to say, inferring context-sensitive stochastic L-systems is possible if inferring context-free L-system is possible.

'''Stochastic L-Systems (S0L):'''

For stochastic L-systems, PMIT-S0L was developed, which uses a hybrid greedy and genetic algorithm approach to infer systems from multiple string sequences. The tool demonstrated the ability to infer rewriting rules and probabilities with high accuracy, a first in the field.

'''Temporal Parametric L-Systems:'''

McQuillan first realized that parametric L-systems could be thought of as stochastic L-systems; however, this did not solve the problem of inferring the parametric selection rules. Using Cartesian Genetic Programming, parametric L-systems could be inferred along with the parametric selection rules so long as the parameter set included time (in order to, provide a sequence to the parameters, but time is a reasonable parameter for any real process). This tool, PMIT-PARAM, successfully inferred complex systems with up to 27 rewriting rules, setting a new benchmark in L-system inference.