View source for L-system

{{Short description|Rewriting system and type of formal grammar}}
{{multiple issues|
{{More citations needed|date=April 2013}}
{{Textbook|date=August 2020}}
}}

[[File:Dragon trees.jpg|thumb|upright=1.5|L-system trees form realistic models of natural patterns]]

An '''L-system''' or '''Lindenmayer system''' is a [[wikt:parallel|parallel]] [[rewriting system]] and a type of [[formal grammar]]. An L-system consists of an [[alphabet]] of symbols that can be used to make [[string (computer science)|string]]s, a collection of [[Production (computer science)|production rule]]s that expand each symbol into some larger string of symbols, an initial "[[axiom]]" string from which to begin construction, and a mechanism for translating the generated strings into geometric structures. L-systems were introduced and developed in 1968 by [[Aristid Lindenmayer]], a Hungarian theoretical [[biologist]] and [[botanist]] at the [[Utrecht University|University of Utrecht]].<ref>{{Cite journal|last=Lindenmayer|first=Aristid|date=March 1968|title=Mathematical models for cellular interactions in development II. Simple and branching filaments with two-sided inputs|journal=Journal of Theoretical Biology|volume=18|issue=3|pages=300–315|doi=10.1016/0022-5193(68)90080-5|pmid=5659072|bibcode=1968JThBi..18..300L|issn=0022-5193}}</ref> Lindenmayer used L-systems to describe the behaviour of plant cells and to model the growth processes of [[plant development]]. L-systems have also been used to model the morphology of a variety of organisms<ref>Grzegorz Rozenberg and Arto Salomaa. The mathematical theory of L systems (Academic Press, New York, 1980). {{ISBN|0-12-597140-0}}</ref> and can be used to generate self-similar [[fractal]]s.

==Origins==
[[File:Fractal weeds.jpg|thumb|upright=1.5|'Weeds', generated using an L-system in 3D.]]
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|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. Later on, this system was extended to describe higher plants and complex branching structures.

==L-system structure==
The [[recursion|recursive]] nature of the L-system rules leads to [[self-similarity]] and thereby, [[fractal]]-like forms are easy to describe with an L-system.   Plant models and natural-looking organic forms are easy to define, as by increasing the recursion level the form slowly 'grows' and becomes more complex. Lindenmayer systems are also popular in the generation of [[artificial life]].

L-system grammars are very similar to the [[semi-Thue grammar]] (see [[Chomsky hierarchy]]).  L-systems are now commonly known as ''parametric'' L systems, defined as a [[tuple]]

:'''G''' = (''V'', ω, ''P''),

where

* '''V''' (the ''alphabet'') is a set of symbols containing both elements that can be replaced (''variables'') and those which cannot be replaced ("constants" or "terminals")
* '''ω''' (''start'', ''axiom'' or ''initiator'') is a string of symbols from '''V''' defining the initial state of the system
* '''P''' is a set of ''[[Production (computer science)|production rule]]s'' or ''productions'' defining the way variables can be replaced with combinations of constants and other variables. A production consists of two strings, the ''predecessor'' and the ''successor''. For any symbol A which is a member of the set V which does not appear on the left hand side of a production in P, the identity production A → A is assumed; these symbols are called ''constants'' or ''terminals''. (See [[Law of identity]]).

The rules of the L-system grammar are applied iteratively starting from the initial state. As many rules as possible are applied simultaneously, per iteration. The fact that each iteration employs as many rules as possible differentiates an L-system from a [[formal language]] generated by a [[formal grammar]], which applies only one rule per iteration. If the production rules were to be applied only one at a time, one would quite simply generate a string in a language, and all such sequences of applications would produce the language specified by the grammar.  There are some strings in some languages, however, that cannot be generated if the grammar is treated as an L-system rather than a language specification. For example,<ref>{{cite web |title=L-systems |url=https://encyclopediaofmath.org/index.php?title=L-systems&oldid=47547 |website=Encyclopedia of Mathematics |publisher=Springer |access-date=26 July 2022}}</ref> suppose there is a rule S→SS in a grammar. If productions are done one at a time, then starting from S, we can get first SS, and then, applying the rule again, SSS.  However, if all applicable rules are applied at every step, as in an L-system, then we cannot get this sentential form.  Instead, the first step would give us SS, but the second would apply the rule twice, giving us SSSS. Thus, the set of strings produced by an L-systems from a given grammar is a subset of the formal language defined by the grammar, and if we take a language to be defined as a set of strings, this means that a given L-system is effectively a subset of the formal language defined by the L-system's grammar.

An L-system is ''context-free'' if each production rule refers only to an individual symbol and not to its neighbours. Context-free L-systems are thus specified by a [[context-free grammar]]. If a rule depends not only on a single symbol but also on its neighbours, it is termed a ''context-sensitive'' L-system.

If there is exactly one production for each symbol, then the L-system is said to be ''deterministic'' (a deterministic context-free L-system is popularly called a ''[[D0L system]]''). If there are several, and each is chosen with a certain probability during each iteration, then it is a ''stochastic'' L-system.

Using L-systems for generating graphical images requires that the symbols in the model refer to elements of a drawing on the computer screen. For example, the program ''[[Fractint]]'' uses [[turtle graphics]] (similar to those in the [[Logo programming language]]) to produce screen images. It interprets each constant in an L-system model as a turtle command.

==Examples of L-systems==

===Example 1: algae===
Lindenmayer's original L-system for modelling the growth of algae.

:'''variables''' :   A B
:'''constants''' :   none
:'''axiom'''     :   A
:'''rules'''     :   (A → AB), (B → A)

which produces:

:     ''n'' = 0 : A
:     ''n'' = 1 : AB
:     ''n'' = 2 : ABA
:     ''n'' = 3 : ABAAB
:     ''n'' = 4 : ABAABABA
:     ''n'' = 5 : ABAABABAABAAB
:     ''n'' = 6 : ABAABABAABAABABAABABA
:     ''n'' = 7 : ABAABABAABAABABAABABAABAABABAABAAB

==== Example 1: algae, explained ====
 n=0:               A             start (axiom/initiator)
                   / \
 n=1:             A   B           the initial single A spawned into AB by rule (A → AB), rule (B → A) couldn't be applied
                 /|     \
 n=2:           A B      A        former string AB with all rules applied, A spawned into AB again, former B turned into A
              / | |       | \
 n=3:         A B A       A B     note all A's producing a copy of themselves in the first place, then a B, which turns ...
            / | | | \     | \ \
 n=4:       A B A A B     A B A   ... into an A one generation later, starting to spawn/repeat/recurse then

The result is the sequence of [[Fibonacci word]]s. If one counts the length of each string, the [[Fibonacci sequence]] of numbers is obtained (skipping the first 1, due to the choice of axiom):

:    1  2  3  5  8  13  21  34  55 89 ...

If it is not desired to skip the first 1, axiom ''B'' can be used. That would place ''B'' node before the topmost node (''A'') of the graph above.

For each string, if one counts the ''k''-th position from the left end of the string, the value is determined by whether a multiple of the [[golden ratio]] falls within the interval <math>(k-1, k)</math>. The ratio of A to B likewise converges to the golden mean.

This example yields the same result (in terms of the length of each string, not the sequence of ''A''s and ''B''s) if the rule (''A'' → ''AB'') is replaced with (''A'' → ''BA''), except that the strings are mirrored.

This sequence is a [[locally catenative sequence]] because <math>G(n)=G(n-1)G(n-2)</math>, where <math>G(n)</math> is the ''n''-th generation.

===Example 2: fractal (binary) tree===
* '''variables''' : 0, 1
* '''constants''': "[", "]"
* '''axiom'''  : 0
* '''rules'''  : (1 → 11), (0 → 1[0]0)

The shape is built by [[recursion|recursively]] feeding the axiom through the production rules. Each character of the input string is checked against the rule list to determine which character or string to replace it with in the output string. In this example, a '1' in the input string becomes '11' in the output string, while '<nowiki>[</nowiki>' remains the same. Applying this to the axiom of '0', one gets:

{|
|-
| axiom: || 0
|-
| 1st recursion: || 1<nowiki>[0]</nowiki>0
|-
| 2nd recursion: || <nowiki>11[1[0]0]1[0]0</nowiki>
|-
| 3rd recursion: || <nowiki>1111[11[1[0]0]1[0]0]11[1[0]0]1[0]0</nowiki>
|-
| ...
|}

It can be seen that this string quickly grows in size and complexity. This string can be drawn as an image by using [[turtle graphics]], where each symbol is assigned a graphical operation for the turtle to perform. For example, in the sample above, the turtle may be given the following instructions:

* 0: draw a [[line segment]] ending in a leaf
* 1: draw a line segment
* <nowiki>[</nowiki>: push position and angle, turn left 45 degrees
* <nowiki>]</nowiki>: pop position and angle, turn right 45 degrees

The push and pop refer to a [[LIFO (computing)|LIFO]] stack (more technical grammar would have separate symbols for "push position" and "turn left"). When the turtle interpretation encounters a '<nowiki>[</nowiki>', the current position and angle are saved, and are then restored when the interpretation encounters a '<nowiki>]</nowiki>'. If multiple values have been "pushed," then a "pop" restores the most recently saved values. Applying the graphical rules listed above to the earlier recursion, one gets:

{{Gallery
|width=150
|File:Graftal0.png|Axiom
|File:Graftal1.png|First recursion
|File:Graftal2.png|Second recursion
|File:Graftal3.png|Third recursion
|File:Graftal4.png|Fourth recursion
|File:Graftal7.png|Seventh recursion, scaled down ten times
}}

===Example 3: Cantor set===
[[File:Cantor set in seven iterations.svg|450px|right]]
:     '''variables''' :   A B
:     '''constants''' :   none
:     '''start'''     :   A   {starting character string}
:     '''rules'''     :   (A → ABA), (B → BBB)

Let ''A'' mean "draw forward" and ''B'' mean "move forward".

This produces the famous [[Cantor set|Cantor's fractal set]] on a real straight line '''R'''.

===Example 4: Koch curve===
A variant of the [[Koch snowflake|Koch curve]] which uses only right angles.

: '''variables''' :   F
: '''constants''' :   + &minus;
: '''start'''     :   F
: '''rules'''     :   (F → F+F&minus;F&minus;F+F)

Here, F means "draw forward", + means "turn left 90°", and &minus; means "turn right 90°" (see [[turtle graphics]]).

: ''n'' = 0:
:: F
:: [[File:square koch.svg|Koch Square - 0 iterations]]

: ''n'' = 1:
:: F+F&minus;F&minus;F+F
:: [[File:square koch 1.svg|Koch Square - 1 iterations]]

: ''n'' = 2:
:: F+F&minus;F&minus;F+F+F+F&minus;F&minus;F+F&minus;F+F&minus;F&minus;F+F&minus;F+F&minus;F&minus;F+F+F+F&minus;F&minus;F+F
:: [[File:square koch 2.svg|Koch Square - 2 iterations]]

: ''n'' = 3:
:: F+F&minus;F&minus;F+F+F+F&minus;F&minus;F+F&minus;F+F&minus;F&minus;F+F&minus;F+F&minus;F&minus;F+F+F+F&minus;F&minus;F+F+
::F+F&minus;F&minus;F+F+F+F&minus;F&minus;F+F&minus;F+F&minus;F&minus;F+F&minus;F+F&minus;F&minus;F+F+F+F&minus;F&minus;F+F&minus;
:: F+F&minus;F&minus;F+F+F+F&minus;F&minus;F+F&minus;F+F&minus;F&minus;F+F&minus;F+F&minus;F&minus;F+F+F+F&minus;F&minus;F+F&minus;
:: F+F&minus;F&minus;F+F+F+F&minus;F&minus;F+F&minus;F+F&minus;F&minus;F+F&minus;F+F&minus;F&minus;F+F+F+F&minus;F&minus;F+F+
:: F+F&minus;F&minus;F+F+F+F&minus;F&minus;F+F&minus;F+F&minus;F&minus;F+F&minus;F+F&minus;F&minus;F+F+F+F&minus;F&minus;F+F
:: [[File:square koch 3.svg|Koch Square - 3 iterations]]

===Example 5: Sierpinski triangle===
The [[Sierpinski triangle]] drawn using an L-system.

:     '''variables''' :   F G
:     '''constants''' :   + &minus;
:     '''start'''     :   F&minus;G&minus;G
:     '''rules'''     :   (F → F&minus;G+F+G&minus;F), (G → GG)
:     '''angle'''     :   120°

Here, F and G both mean "draw forward", + means "turn left by angle", and &minus; means "turn right by angle".

<gallery mode="nolines" widths="256px" heights="256px">
File:Sierpinski Triangle (from L-System, 2 iterations).png|n = 2
File:Sierpinski Triangle (from L-System, 4 iterations).png|n = 4
File:Sierpinski Triangle (from L-System, 6 iterations).png|n = 6
</gallery>

It is also possible to approximate the [[Sierpinski triangle]] using a [[Sierpiński arrowhead curve]] L-system.

:     '''variables''' :   A B
:     '''constants''' :   + &minus;
:     '''start'''     :   A
:     '''rules'''     :   (A → B&minus;A&minus;B), (B → A+B+A)
:     '''angle'''     :   60°

Here, A and B both mean "draw forward", + means "turn left by angle", and &minus; means "turn right by angle" (see [[turtle graphics]]).

[[File:Serpinski Lsystem.svg|centre]]
{{center|1=Evolution for ''n'' = 2, ''n'' = 4, ''n'' = 6, ''n'' = 8}}

===Example 6: dragon curve ===
The [[dragon curve]] drawn using an L-system.

:     '''variables''' :   F G
:     '''constants''' :   + −
:     '''start'''     :   F
:     '''rules'''     :   (F → F+G), (G → F-G)
:     '''angle'''     :   90°

Here, F and G both mean "draw forward", + means "turn left by angle", and − means "turn right by angle".

[[File:Dragon curve L-system.svg|centre|400px]]

{{center|1=Dragon curve for ''n'' = 10}}

===Example 7: fractal plant ===
{{See also|Barnsley fern}}

:     '''variables''' :   X F
:     '''constants''' :   + &minus; [ ]
:     '''start'''     :   -X
:     '''rules'''     :   (X → F+[[X]-X]-F[-FX]+X), (F → FF)
:     '''angle'''     :   25°

First one needs to initialize an empty stack. This follows the LIFO (Last in, First Out) method to add and remove elements. 
Here, F means "draw forward", − means "turn right 25°", and + means "turn left 25°". X does not correspond to any drawing action and is used to control the evolution of the curve. The square bracket "[" corresponds to saving the current values for position and angle, so the position and angle are pushed to the top of the stack, when the "]" token is encountered, the stack is popped and the position and angle are reset. Every "[" comes before every "]" token.

[[File:Fractal-plant.svg|alt=|left]][[File:Fractal_Farn.gif|alt=]]{{center|1=Fractal plant for ''n'' = 6}}

==Variations==
A number of elaborations on this basic L-system technique have been developed which can be used in conjunction with each other. Among these are [[stochastic grammar]]s, [[context sensitive grammar]]s, and parametric grammars.

===Stochastic grammars===
The grammar model we have discussed thus far has been deterministic—that is, given any symbol in the grammar's alphabet, there has been exactly one production rule, which is always chosen, and always performs the same conversion. One alternative is to specify more than one production rule for a symbol, giving each a [[probability]] of occurring. For example, in the grammar of Example 2, we could change the rule for rewriting "0" from:

:0 → 1[0]0

to a probabilistic rule:

:0 (0.5) → 1[0]0
:0 (0.5) → 0

Under this production, whenever a "0" is encountered during string rewriting, there would be a 50% chance it would behave as previously described, and a 50% chance it would not change during production. When a stochastic grammar is used in an [[evolution]]ary context, it is advisable to incorporate a [[random]] seed into the [[genotype]], so that the stochastic properties of the image remain constant between generations.

===Context sensitive grammars===
A context sensitive production rule looks not only at the symbol it is modifying, but the symbols on the string appearing before and after it. For instance, the production rule:

:b < a > c → aa

transforms "a" to "aa", but only if the "a" occurs between a "b" and a "c" in the input string:

:…bac…

As with stochastic productions, there are multiple productions to handle symbols in different contexts. If no production rule can be found for a given context, the identity production is assumed, and the symbol does not change on transformation. If context-sensitive and context-free productions both exist within the same grammar, the context-sensitive production is assumed to take precedence when it is applicable.

===Parametric grammars===
In a parametric grammar, each symbol in the alphabet has a parameter list associated with it. A symbol coupled with its parameter list is called a module, and a string in a parametric grammar is a series of modules. An example string might be:

:a(0,1)[b(0,0)]a(1,2)

The parameters can be used by the drawing functions, and also by the production rules. The production rules can use the parameters in two ways: first, in a conditional statement determining whether the rule will apply, and second, the production rule can modify the actual parameters. For example, look at:

:a(x,y) : x == 0 → a(1, y+1)b(2,3)

The module a(x,y) undergoes transformation under this production rule if the conditional x=0 is met. For example, a(0,2) would undergo transformation, and a(1,2) would not.

In the transformation portion of the production rule, the parameters as well as entire modules can be affected. In the above example, the module b(x,y) is added to the string, with initial parameters (2,3). Also, the parameters of the already existing module are transformed. Under the above production rule,

:a(0,2)

Becomes

:a(1,3)b(2,3)

as the "x" parameter of a(x,y) is explicitly transformed to a "1" and the "y" parameter of a is incremented by one.

Parametric grammars allow line lengths and branching angles to be determined by the grammar, rather than the turtle interpretation methods. Also, if age is given as a parameter for a module, rules can change depending on the age of a plant segment, allowing animations of the entire life-cycle of the tree to be created.

===Bi-directional grammars===
The bi-directional model explicitly separates the symbolic rewriting system from the shape assignment. For example, the string rewriting process in the Example 2 (Fractal tree) is independent on how graphical operations are assigned to the symbols. In other words, an infinite number of draw methods are applicable to a given rewriting system.

The bi-directional model consists of 1) a forward process constructs the derivation tree with production rules, and 2) a backward process realizes the tree with shapes in a stepwise manner (from leaves to the root). Each inverse-derivation step involves essential geometric-topological reasoning. With this bi-directional framework, design constraints and objectives are encoded in the grammar-shape translation. In architectural design applications, the bi-directional grammar features consistent interior connectivity and a rich spatial hierarchy.<ref>Hua, H., 2017, December. [https://www.researchgate.net/profile/Hao_Hua/publication/311357805_A_Bi-Directional_Procedural_Model_for_Architectural_Design/links/5a29fb8baca2728e05dafa4b/A-Bi-Directional-Procedural-Model-for-Architectural-Design.pdf A Bi‐Directional Procedural Model for Architectural Design]. In Computer Graphics Forum (Vol. 36, No. 8, pp. 219-231).</ref>

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

== Open problems ==
There are many open problems involving studies of L-systems. For example:

* Characterisation of all the deterministic context-free L-systems which are [[locally catenative sequence|locally catenative]]. (A complete solution is known only in the case where there are only two variables).<ref>{{Cite book | doi=10.1007/978-3-642-59136-5_5|chapter = L Systems|title = Handbook of Formal Languages| pages=253–328|year = 1997|last1 = Kari|first1 = Lila| last2=Rozenberg| first2=Grzegorz| last3=Salomaa| first3=Arto| isbn=978-3-642-63863-3}}</ref>

== Types of L-systems ==
L-systems on the [[real number|real line]] '''R''':
*[[Prouhet-Thue-Morse system]]

Well-known L-systems on a plane '''R'''<sup>2</sup> are: 
* [[space-filling curve]]s ([[Hilbert curve]], [[Peano's curve]]s, Dekking's church, [[kolam]]s),
* median space-filling curves ([[Lévy C curve]], [[dragon curve|Harter-Heighway dragon curve]], Davis-Knuth terdragon),
* tilings ([[sphinx tiling]], [[Penrose tiling]])

==See also==
{{Commons category|L-systems}}
* [[Digital morphogenesis]]
* [[Iterated function system]]
* {{annotated link|Reaction–diffusion system}} that provides diffusing-chemical-reagent simulations (including Life-like)
* [[Stochastic context-free grammar]]
* ''[[The Algorithmic Beauty of Plants]]''

== Notes ==
{{Reflist}}

==Books==
* [[Przemysław Prusinkiewicz]], [[Aristid Lindenmayer]] – [[The Algorithmic Beauty of Plants]] [https://algorithmicbotany.org/papers/#abop PDF version available here for free] {{Webarchive|url=https://web.archive.org/web/20210410150043/https://algorithmicbotany.org/papers/#abop |date=2021-04-10 }}
* [[Grzegorz Rozenberg]], [[Arto Salomaa]] – ''Lindenmayer Systems: Impacts on Theoretical Computer Science, Computer Graphics, and Developmental Biology'' {{ISBN|978-3-540-55320-5}}
* D.S. Ebert, F.K. Musgrave, et al. – ''Texturing and Modeling: A Procedural Approach'', {{ISBN|0-12-228730-4}}
* Burry, Jane, Burry Mark, (2010). The New Mathematics of Architecture, New York: Thames and Hudson.
* Aristid Lindenmayer, "[https://www0.cs.ucl.ac.uk/staff/p.bentley/teaching/L6_reading/lsystems.pdf Mathematical models for cellular interaction in development]." J. Theoret. Biology, 18:280—315, 1968.

==External links==
{{Div col}}
* [https://algorithmicbotany.org/ Algorithmic Botany at the University of Calgary]
* [https://rue-a.github.io/L-Systems/ L-Systems]: A user friendly page to generate fractals and plants from L-Systems.
* [https://www.mizuno.org/applet/branching/ Branching: L-system Tree]　A [[Java applet]] and its [[source code]] ([[Open-source software|open source]]) of the botanical tree growth simulation using the L-system.
* [https://web.archive.org/web/20020503212834/https://spanky.triumf.ca/WWW/FRACTINT/lsys/truefractal.html Fractint L-System True Fractals]
*[https://openalea.gforge.inria.fr/ OpenAlea] {{Webarchive|url=https://web.archive.org/web/20051017111619/https://openalea.gforge.inria.fr/ |date=2005-10-17 }}: an open-source software environment for plant modeling,<ref>{{cite book |doi=10.1145/2791347.2791365 |pages=1–6 |year=2015 |last1=Pradal |first1=Christophe |last2=Fournier |first2=Christian |last3=Valduriez |first3=Patrick |last4=Cohen-Boulakia |first4=Sarah |title=Proceedings of the 27th International Conference on Scientific and Statistical Database Management |chapter=OpenAlea |author4-link=Sarah Cohen-Boulakia|isbn=9781450337090|s2cid=14246115 |url=https://hal.archives-ouvertes.fr/hal-01166298/file/openalea-PradalCohen-Boulakia.pdf |archive-url=https://web.archive.org/web/20191017173603/https://hal.archives-ouvertes.fr/hal-01166298/file/openalea-PradalCohen-Boulakia.pdf |archive-date=2019-10-17 |url-status=live }}</ref> which contains [https://github.com/openalea/lpy L-Py], an open-source python implementation of the Lindenmayer systems<ref>{{cite journal |doi=10.3389/fpls.2012.00076 |pmid=22670147 |pmc=3362793 |title=L-Py: An L-System Simulation Framework for Modeling Plant Architecture Development Based on a Dynamic Language |journal=Frontiers in Plant Science |volume=3 |pages=76 |year=2012 |last1=Boudon |first1=Frédéric |last2=Pradal |first2=Christophe |last3=Cokelaer |first3=Thomas |last4=Prusinkiewicz |first4=Przemyslaw |last5=Godin |first5=Christophe|doi-access=free }}</ref>
* [https://sourceforge.net/projects/pplant/ "powerPlant" an open-source landscape modelling software]
* [https://www.cs.ucl.ac.uk/staff/W.Langdon/pfeiffer.html An evolutionary L-systems generator (anyos*)]
* [https://github.com/rfindler/lindenmayer/ An implementation of L-systems in Racket]
* {{cite web|url=https://www.pawfal.org/index.php?page=LsystemComposition|title=LsystemComposition|last=Griffiths|first=Dave|year=2004|website=Pawfal|language=en|access-date=2012-04-19|archive-url=https://web.archive.org/web/20041106154657/https://www.pawfal.org/index.php?page=LsystemComposition|archive-date=2004-11-06|url-status=live}} Page about using L-systems and [[genetic algorithm]]s to generate music.
*[https://www.grogra.de/ eXtended L-Systems (XL), Relational Growth Grammars, and open-source software platform GroIMP.]
*[https://to-campos.planetaclix.pt/fractal/plantae.htm A JAVA applet with many fractal figures generated by L-systems.] {{Webarchive|url=https://web.archive.org/web/20160806081808/https://to-campos.planetaclix.pt/fractal/plantae.htm |date=2016-08-06 }}
*{{Cite thesis |last=Manousakis |first=Stelios |title=Musical L-Systems |date=June 2006 |degree=Master's |publisher=[[Royal Conservatory of The Hague]] |url=https://www.modularbrains.net/support/SteliosManousakis-Musical_L-systems.pdf |archive-url=https://web.archive.org/web/20110723211305/http://www.modularbrains.net/support/SteliosManousakis-Musical_L-systems.pdf |archive-date=2011-07-23 |url-status=live |language=en |access-date=2022-07-19}}
*[https://jsxgraph.uni-bayreuth.de/wiki/index.php/L-systems Online experiments with L-Systems using JSXGraph (JavaScript)]
* [https://flea.sourceforge.net/ Flea] A Ruby implementation of LSYSTEM, using a Domain Specific Language instead of terse generator commands
* [https://madflame991.blogspot.com/p/lindenmayer-power.html Lindenmayer power] A plant and fractal generator using L-systems (JavaScript)
* {{SpringerEOM|title=L-systems|id=L-systems&oldid=14908|last1=Rozenberg|first1=G.|last2=Salomaa|first2=A.}}
* [https://laurenslapre.nl/lapre_004.htm Laurens Lapré's L-Parser] {{Webarchive|url=https://web.archive.org/web/20130913220627/https://laurenslapre.nl/lapre_004.htm |date=2013-09-13 }}
* [https://www.kevs3d.co.uk/dev/lsystems/ HTML5 L-Systems – try out experiments online]
* [https://inkscape.org/ The vector-graphics program] [[Inkscape]] features an L-System Parser
* {{cite journal|doi=10.1002/cplx.20291|title=Modeling complexity in musical rhythm|date=2009 |last1=Liou |first1=Cheng-Yuan |last2=Wu |first2=Tai-Hei |last3=Lee |first3=Chia-Ying |journal=Complexity |volume=15 |issue=4 |pages=19–30 |s2cid=18737938 }}
* [https://xojoc.pw/dailyprogrammer/fractals.html An implementation of a L-system parser and simple turtle graphics in the Icon programming language]
* [https://nolandc.com/sandbox/fractals/ A Lindenmeyer System Generator by Nolan Carroll]
* [https://bloogen.com/ Bloogen: L-Systems with a genetic twist]
* [https://harvest.usask.ca/bitstream/10388/13620/8/BERNARD-DISSERTATION-2020.pdf Inferring Different Types of Lindenmayer Systems Using Artificial Intelligence]

{{Div col end}}

{{Fractals}}
{{Authority control}}

[[Category:L-systems| ]]