Lyndenmeyer Systems

PROCEDURAL COMPOSITION TUTORIAL
L-Systems: Some History

   Lindenmayer systems (L-systems) were initially conceived by Aristid Lyndenmeyer as a mathematical theory of elementary plant development. The emphasis was on the spatial relations between cells or larger plant modules. Lindenmayer's original work (Lindenmayer 1982) was restricted to a basic topological model.
Early Origins

   Subsequently, several geometric interpretations of L-systems were proposed with a view to turning them into a more versatile tool for modelling entire plant topologies. Turtle Geometry (Prusinkiewicz 1986), for example, has proven to be a particularly useful.
Turtle geometry

   The first results in modelling higher plants were (Frijters and Lindenmayer 1974), and (Hogeweg and Hesper 1974). In both cases, a more sophisticated graphical interpretation of L-systems was used which enabled the branching topology of the plants to be modelled. Geometric aspects, such as the lengths of stem segments and the angle of the stems relatice to one-another and the stem, were added in a post-processing phase. By extendeding the work of Hogeweg and Hesper, Smith demonstrating the potential of L-systems for the synthesis of realistic images. (Smith 1978) and (Smith 1984).
Geometric modelling
and image synthesis

Using techniques such as chain coding (Freeman 1961), (Szilard and Quinton 1979) refined a geometry for representing images and showed that very simple DOL-systems could generate fractals curves (Mandelbrot 1982). This work was extended by Dekking, who explored the limit properties of curves generated by Lsystems (Dekking 1982a) and the fractal (Hausdorff) dimension of the limit set (Dekking 1982b). Concurrently, Siromoney and Subramanian (Siromoney and Subramanian 1983) specified L-systems which generate classic space-filling curves.
Fractals
Space-filling curves

   Further applications of L-systems based on a LOGO-style turtle (Abelson and diSessa 1982), include:

Examples of fractals and plant-like structures (Prusinkiewicz 1986) and (Prusinkiewicz 1987).
Realistic modelling of herbaceous plants (Prusinkiewicz, Lindenmayer and Hanan 1988).
Southern Indian kolam patterns (Prusinkiewicz and Hanan 1989), (Prusinkiewicz, Krithivasan and Vijayanarayana 1989), (Siromoney and Siromoney 1987) and (Siromoney, Siromoney and Robinsin 1989).
Synthesis of musical scores (Prusinkiewicz 1986), and karnatic music (Prusinkiewicz, Krithivasan and Vijayanarayana 1989).
Automatic generation of spacefilling curves (Prusinkiewicz, Lindenmayer and Pracchia 1990).

Further applications

For example, Wolfram [160, 161] studied patterns generated by rewriting elements of rectangular arrays. A similar array-rewriting mechanism is the cornerstone of Conway's popular game of life [49, 50].
An important body of research has been devoted to various graph-rewriting systems [14, 33, 34]. The most extensively studied and the best understood rewriting systems operate on character strings. The first formal definition of such a system was given at the beginning of this century by Thue [128], but a wide interest in string rewriting was spawned in the late 1950s by Chomsky's work on formal grammars [13]. He applied the concept of rewriting to describe the syntactic features of natural languages. A few years later Backus and Naur introduced a rewriting-based notation in order to provide a formal definition of the programming language ALGOL-60 [5, 103]. The equivalence of the Backus-Naur form (BNF) and the context-free class of Chomsky grammars was soon recognized [52], and a period of fascination with syntax, grammars and their application to computer science began.
At the center of attention were sets of strings -called formal languages- and the methods for generating, recognizing and transforming them. In 1968 a biologist, Arisrid Lindenmayer, introduced a new type of string-rewriting mechanism, subsequently termed L-systems [82]. The essential difference between Chomsky grammars and L-systems lies in the method of applying productions. In Chomsky grammars productions are applied sequentially, whereas in L-systems they are applied in parallel and simultaneously replace all letters in a given word. This difference reflects the biological motivation of L-systems. Productions are intended to capture cell divisions in multicellular organisms, where many divisions may occur at the same time.
Parallel production application has an essential impact on the formal properties of rewriting systems. For example, there are languages which can be generated by context-free L-systems (called OL-systems) but not by context-free Chomsky grammars [62, 128] (Figure 1.2).
Rewriting systems

Lindenmayer systems (L-systems) were initially conceived by Aristid Lyndenmeyer as a mathematical theory of elementary plant development. The emphasis was on the spatial relations between cells or larger plant modules. Lindenmayer's original work (Lindenmayer 1982) was restricted to a basic topological model.	Early Origins
Subsequently, several geometric interpretations of L-systems were proposed with a view to turning them into a more versatile tool for modelling entire plant topologies. Turtle Geometry (Prusinkiewicz 1986), for example, has proven to be a particularly useful.	Turtle geometry
The first results in modelling higher plants were (Frijters and Lindenmayer 1974), and (Hogeweg and Hesper 1974). In both cases, a more sophisticated graphical interpretation of L-systems was used which enabled the branching topology of the plants to be modelled. Geometric aspects, such as the lengths of stem segments and the angle of the stems relatice to one-another and the stem, were added in a post-processing phase. By extendeding the work of Hogeweg and Hesper, Smith demonstrating the potential of L-systems for the synthesis of realistic images. (Smith 1978) and (Smith 1984).	Geometric modelling and image synthesis
Using techniques such as chain coding (Freeman 1961), (Szilard and Quinton 1979) refined a geometry for representing images and showed that very simple DOL-systems could generate fractals curves (Mandelbrot 1982). This work was extended by Dekking, who explored the limit properties of curves generated by Lsystems (Dekking 1982a) and the fractal (Hausdorff) dimension of the limit set (Dekking 1982b). Concurrently, Siromoney and Subramanian (Siromoney and Subramanian 1983) specified L-systems which generate classic space-filling curves.	Fractals Space-filling curves
Further applications of L-systems based on a LOGO-style turtle (Abelson and diSessa 1982), include: Examples of fractals and plant-like structures (Prusinkiewicz 1986) and (Prusinkiewicz 1987). Realistic modelling of herbaceous plants (Prusinkiewicz, Lindenmayer and Hanan 1988). Southern Indian kolam patterns (Prusinkiewicz and Hanan 1989), (Prusinkiewicz, Krithivasan and Vijayanarayana 1989), (Siromoney and Siromoney 1987) and (Siromoney, Siromoney and Robinsin 1989). Synthesis of musical scores (Prusinkiewicz 1986), and karnatic music (Prusinkiewicz, Krithivasan and Vijayanarayana 1989). Automatic generation of spacefilling curves (Prusinkiewicz, Lindenmayer and Pracchia 1990).	Further applications
For example, Wolfram [160, 161] studied patterns generated by rewriting elements of rectangular arrays. A similar array-rewriting mechanism is the cornerstone of Conway's popular game of life [49, 50]. An important body of research has been devoted to various graph-rewriting systems [14, 33, 34]. The most extensively studied and the best understood rewriting systems operate on character strings. The first formal definition of such a system was given at the beginning of this century by Thue [128], but a wide interest in string rewriting was spawned in the late 1950s by Chomsky's work on formal grammars [13]. He applied the concept of rewriting to describe the syntactic features of natural languages. A few years later Backus and Naur introduced a rewriting-based notation in order to provide a formal definition of the programming language ALGOL-60 [5, 103]. The equivalence of the Backus-Naur form (BNF) and the context-free class of Chomsky grammars was soon recognized [52], and a period of fascination with syntax, grammars and their application to computer science began. At the center of attention were sets of strings -called formal languages- and the methods for generating, recognizing and transforming them. In 1968 a biologist, Arisrid Lindenmayer, introduced a new type of string-rewriting mechanism, subsequently termed L-systems [82]. The essential difference between Chomsky grammars and L-systems lies in the method of applying productions. In Chomsky grammars productions are applied sequentially, whereas in L-systems they are applied in parallel and simultaneously replace all letters in a given word. This difference reflects the biological motivation of L-systems. Productions are intended to capture cell divisions in multicellular organisms, where many divisions may occur at the same time. Parallel production application has an essential impact on the formal properties of rewriting systems. For example, there are languages which can be generated by context-free L-systems (called OL-systems) but not by context-free Chomsky grammars [62, 128] (Figure 1.2).	Rewriting systems