L-system
L-systems were introduced and developed in 1968 by Aristid Lindenmayer, a Hungarian theoretical biologist and botanist at the University of Utrecht.
As a biologist, Lindenmayer worked with yeast and filamentous fungi and studied the growth patterns of various types of bacteria, such as the cyanobacteria Anabaena catenula.
Originally, the L-systems were devised to provide a formal description of the development of such simple multicellular organisms, and to illustrate the neighbourhood relationships between plant cells.
Using L-systems for generating graphical images requires that the symbols in the model refer to elements of a drawing on the computer screen.
This produces the famous Cantor's fractal set on a real straight line R. A variant of the Koch curve which uses only right angles.
In architectural design applications, the bi-directional grammar features consistent interior connectivity and a rich spatial hierarchy.
[4] Historically, the construction of L-systems relied heavily on manual efforts by experts,[5][6][7] requiring detailed measurements, domain knowledge, and significant time investment.
This labor-intensive method made creating accurate models for complex processes both tedious and error-prone.
A notable example is Nishida's [7] 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 [6] 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.
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.
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.
[9][10][11][12] For instance, Nakano's [10] work highlighted the challenges of inferring L-systems with larger alphabets and more complex structures, describing the task as "immensely complicated".
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.
[12][13] However, these tools relied heavily on human judgment and did not fully automate the inference process.
Some early algorithms were tightly integrated into specific research domains mainly plant modeling.
Attempts to create generalized algorithms for L-system inference began with deterministic context-free systems.
These algorithms encountered significant challenges,[14][15] including: Bernard's PhD dissertation,[16] 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.
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 [17] 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.
The tool demonstrated the ability to infer rewriting rules and probabilities with high accuracy, a first in the field.
