Editing L-system (section)

=== 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.