PROCEDURAL COMPOSITION TUTORIAL
LSystems: Some History
Lindenmayer systems (Lsystems) 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 Lsystems 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 Lsystems 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 oneanother and the stem, were added in a postprocessing phase. By extendeding the work of Hogeweg and Hesper, Smith demonstrating the potential of Lsystems for the synthesis of realistic images. (Smith 1978) and (Smith 1984). 
Geometric modelling 
Using techniques such as chain coding (Freeman 1961), (Szilard and Quinton 1979) refined a geometry for representing images and showed that very simple DOLsystems 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 Lsystems which generate classic spacefilling curves. 
Fractals 
Further applications of Lsystems based on a LOGOstyle turtle (Abelson and diSessa 1982), include:

Further applications 
For example, Wolfram [160, 161] studied patterns generated by rewriting elements
of rectangular arrays. A similar arrayrewriting mechanism is the cornerstone of
Conway's popular game of life [49, 50]. An important body of research has been devoted to various graphrewriting 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 rewritingbased notation in order to provide a formal definition of the programming language ALGOL60 [5, 103]. The equivalence of the BackusNaur form (BNF) and the contextfree 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 stringrewriting mechanism, subsequently termed Lsystems [82]. The essential difference between Chomsky grammars and Lsystems lies in the method of applying productions. In Chomsky grammars productions are applied sequentially, whereas in Lsystems they are applied in parallel and simultaneously replace all letters in a given word. This difference reflects the biological motivation of Lsystems. 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 contextfree Lsystems (called OLsystems) but not by contextfree Chomsky grammars [62, 128] (Figure 1.2). 
Rewriting systems 