Chapter 1 Graphical modeling using L-systems

1 Chapter 1 Graphical modeling usingL-systemsLindenmayer systems or L-systems for short were conceived asa mathematical theory of plant development [82]. Originally, they didnot include enough detail to allow for comprehensive modeling of higherplants. The emphasis was on plant topology, that is, the neighborhoodrelations between cells or larger plant modules. Their geometric aspectswere beyond the scope of the theory. Subsequently, several geometricinterpretations of L-systems were proposed with a view to turning theminto a versatile tool for plant modeling .

2 Throughout this book, aninterpretation based on turtle geometry is used [109]. Basic notionsrelated to L- system theory and their turtle interpretation are Rewriting systemsThe central concept of L-systems is that of rewriting. In general, rewrit-ing is a technique for defining complex objects by successively replacingparts of a simple initial object using a set ofrewriting rulesorproduc-tions. The classic example of a Graphical object defined in terms ofrewriting rules is thesnowflake curve(Figure ), proposed in 1905 byKochconstructionvon Koch [155].

3 Mandelbrot [95, page 39] restates this construction asfollows:One begins withtwo shapes,aninitiatorand latter is an oriented broken line made up ofNequalsides of lengthr. Thus each stage of the construction beginswith a broken line and consists in replacing each straightinterval with a copy of the generator, reduced and displacedso as to have the same end points as those of the intervalbeing 1. Graphical modeling using L-systemsinitiatorgeneratorFigure : Construction of the snowflake curveWhile the Koch construction recursively replaces open polygons, rewrit-ing systems that operate on other objects have also been example, Wolfram [160, 161] studied patterns generated by rewrit-ing elements of rectangular arrays.

4 A similar array-rewriting mecha-nism is the cornerstone of Conway s populargame of life[49, 50]. Animportant body of research has been devoted to various graph-rewritingsystems [14, 33, 34].The most extensively studied and the best understood rewriting sys-Grammarstems operate on character strings. The first formal definition of such asystem was given at the beginning of this century by Thue [128], buta wide interest in string rewriting was spawned in the late 1950s byChomsky s work on formal grammars [13].

5 He applied the concept ofrewriting to describe the syntactic features of natural languages. Afew years later Backus and Naur introduced a rewriting-based notationin order to provide a formal definition of the programming languageALGOL-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 appli-cation to computer science began. At the center of attention were setsof strings called formal languages and the methods for generating,recognizing and transforming 1968 a biologist, Aristid Lindenmayer, introduced a new type ofL-systemsstring-rewriting mechanism, subsequently termed L-systems [82].

6 Theessential difference between Chomsky grammars and L-systems lies DOL-systems3 Figure : Relations between Chomsky classes of languages and languageclasses generated by L-systems . The symbols OL and IL denote languageclasses generated by context-free and context-sensitive L-systems , method of applying productions. In Chomsky grammars produc-tions are applied sequentially, whereas in L-systems they are appliedin parallel and simultaneously replace all letters in a given word. Thisdifference reflects the biological motivation of L-systems .

7 Productionsare intended to capture cell divisions in multicellular organisms, wheremany divisions may occur at the same time. Parallel production ap-plication has an essential impact on the formal properties of rewritingsystems. For example, there are languages which can be generatedby context-free L-systems (called OL-systems) but not by context-freeChomsky grammars [62, 128] (Figure ). DOL-systemsThis section presents the simplest class of L-systems , those which aredeterministic and context-free, called DOL-systems.

8 The discussionstarts with an example that introduces the main idea in intuitive strings (words) built of two lettersaandb,whichmayExampleoccur many times in a string. Each letter is associated with a rewritingrule. The rulea abmeans that the letterais to be replaced bythe stringab, and the ruleb ameans that the letterbis to bereplaced bya. The rewriting process starts from a distinguished stringcalled the axiom. Assume that it consists of a single derivation step (the first step of rewriting) the axiombis replaced4 Chapter 1.

9 Graphical modeling using L-systemsFigure : Example of a derivation in a DOL-systembyausing productionb a. In the second stepais replaced byabusing productiona of two letters, both ofwhich aresimultaneouslyreplaced in the next derivation step. Thus,ais replaced byab,bis replaced bya, and the stringabaresults. In asimilar way, the stringabayieldsabaabwhich in turn yieldsabaababa,thenabaababaabaab, and so on (Figure ).Formal definitions describing DOL-systems and their operation aregiven below.

10 For more details see [62, 127].LetVdenote an alphabet,V the set of all words overV,andL-systemV+the set of all nonempty words OL-systemis anordered tripletG= V, , P whereVis thealphabetof the system , V+is a nonempty word called theaxiomandP V V is afiniteset of productions. A production (a, ) Pis written asa . The letteraand the word are called thepredecessorand thesuccessorof this production, respectively. It is assumed that for anylettera V, there is at least one word V such thata .Ifno production is explicitly specified for a given predecessora V,theidentity productiona ais assumed to belong to the set of productionsP.