Advances in Systems Science and Applications (2013) Vol.13 No.2 100-115 Set-Theoretic Design and Analysis of L Systems Xiaojun Duan1, Bing Ju1 and Yi Lin2 1Department of Mathematics and Systems Science, National University of Defense Technology, Changsha 410073, PR China 2Department of Mathematics, Slippery Rock University, Slippery Rock, PA 16057 USA Abstract From the perspective of set theory, this paper establishes a rigorous mathematical definition of L systems, and proves the common characteristics of simple L sys- tems by providing a theoretical framework for a systematic research of L systems. Additionally, explanations for the characteristics of systems’ emergence based on L systems are provided, and some design methods of L systems are developed and interesting cases of design are constructed. This work is the first of its kind that investigates the L system using a rigorous mathematical definition based on set theory. Keywords set theory, L system, characteristics of systems 1 Introduction Although the figures produced out of fractals are generally complicated, the de- scription of fractals can be quite straightforward. Among the commonly utilized methods are the L-system and the IFS (Iterated Function System). In terms of the fractals they respectively describe, the L-system is simpler than the IF sys- tem, where the former contains simple iterations of character strings, while the latter is much more complicated in this regard. Aristid Lindenmayer, a Hungary biologist, introduced the Lindenmayer sys- tem, or L system in short, as the mathematics theory for describing the growth of a plant[1]. It is a kind of subsequent string replacement system; its theory fo- cuses on the topology of plants, and attempts to describe the adjacency relations between cells or between larger plant modules. While Lindenmayer and others proposed the initial solution[1], Prusinkiewicz used turtle graphics to implement a lot of fractal shapes and herb model based on turtle shapes[2]. His works made turtle the most commonly used form and explanatory schemes of L systems. In order to avoid the models constructed using L systems inflexible, Eichhorst and others proposed the concept of stochastic L-systems to enhance the flexibility of the earlier L-models[3]. Herman generalized the concept of L-systems to a context sensitive model in order to establish associations between different modules of the plant model[4]. Then, Lindenmayer introduced parameters to make L-systems even more forthright and efficient. The most typical applications of L-systems are done by scholars at Calgary University, Canada. They were involved in the parametricalization of L-systems, the establishment of differential L-system, open Advances in Systems Science and Applications (2013) Vol.13 No.2 101 L-system, and other relevant theoretical researches[2]. Additionally, they devel- oped the plant simulation software L-Studio[2,5]. Because there has not been any rigorous mathematical definition established for L systems, all published studies on the subject have stayed only at the level of innovative designs without much theoretical support. On the other hand, as shown in (Lin, 1999)[6], set theory is a good tool for the theoretical framework of systemics. In this paper, starting from the basics of set theory, we will develop a rigorous mathematical definition for simple L systems. On the basis of this definition, we establish some of the general properties simple L systems satisfy so that our constructed theoretical framework is expected to provide the needed fundamental ground for further investigation of L systems. 2 The Definition of Simple L Systems The fact is that L-systems represent a formal language; it can be divided into three classes: 0L system, 1L system, and 2L system. A 0L system stands for an L system that is context free. That is, the behavior of each element is solely determined by the rewriting rule; the current state of the system has something to do only with the state of the immediate previous time moment and has noth- ing to do with any surrounding element. Among L systems are 0L systems the simplest; that is why each 0L system is also referred to as a simple L system. Each 1L system stands for a context sensitive L system that considers only one single-sided grammatical relationship. The current state of the system has something to do with not only the state of the immediate previous time moment but also the state of the elements on one side, either left associated or right as- sociated. Each 2L system is also a context sensitive L system that, different of 1L sys- tems, it considers grammatical relationships from both sides. That is, the current state of the system is related to not only the state of the immediate previous time moment, but also the states of the surrounding elements. It represents a method that is most sensitive to the context. These three classes of L systems are further divided into deterministic and ran- dom L systems depending on whether or not the rewrite rules are deterministic. Let S = {s1, s2, . . . , sn} be a finite set of characters of a language, say, En- glish, and S∗ the set of all strings of characters from S. Because S ⊂ S∗, S∗ is a non-empty set. ∀α, β ∈ S∗, define that α = β ⇔ both α and β are identical, meanings that they have the same length and order of the same characters. Now, define the addition operation ⊕ on S∗ as follows: α ⊕ β = αβ = the string of characters of those in α followed by those in β, ∀α, β ∈ S∗. The scalar multiplication on S∗ is defined as follows: ∀α ∈ S∗, k ∈ Z+ = the set of all whole 102 Xiaojun Duan:Set-Theoretic Design and Analysis of L Systems numbers, kα = αα . . . α︸ ︷︷ ︸ k times . Then, the following properties can be shown: (1)Both addition and scalar multiplication defined on S∗ are closed; (2)(α⊕ β)⊕ γ = α⊕ (β ⊕ γ),∀α, β, γ ∈ S∗; (3)k(lα) = (kl)α,(α⊕ β)⊕ γ = α⊕ (β ⊕ γ),∀α, β, γ ∈ S∗;and (4)(k + l)α = kα⊕ lα,∀α ∈ S∗, k, l ∈ Z+. Before we develop a rigorous definition of simple L systems, let us first look at a specific mapping S∗ → S∗, known as L mapping. 2.1 The L Mapping Definition 2.1(Production rules). For any si ∈ S, 1 ≤ i ≤ n, if an ordered pair (si, α) ∈ S × S∗ can be defined, then this pair defines a relation pi from si to α, known as a production rule from S to S∗. Definition 2.2 (Same class production rules). For a given si ∈ S, if there are r ≥ 1 production rules p (1) i , p (2) i , . . . , p (r) i defined for si such that ∀j ̸= k(1 ≤ j, k ≤ r), p (j) i (si) ̸= p (k) i (si), then p (1) i , p (2) i , . . . , p (r) i are referred to as r same class production rules of the character si, and Pi = {p(1)i , p (2) i , . . . , p (r) i } the set of same class production rules of the character si. Definition 2.3 (L mapping). Suppose that m(≥ n) production rules P = n∪ i=1 Pi from S to S∗ are given, where each Pi is non-empty and stands for the same class production rules of the character si ∈ S, 1 ≤ i ≤ n. For any group of production rules p1, p2, . . . , pn ∈ P , satisfying pi ∈ Pi, i = 1, 2, . . . , n, the set φ = {p1, p2, . . . , pn} defines a mapping S∗ → S∗, still denoted φ, by φ : sk1sk2 . . . skr → pk1(sk1)pk2(sk2) . . . pkr(skr) (1) ∀sk1sk2 . . . skr ∈ S∗, ki ∈ {1, 2, . . . , n}, 1 ≤ i ≤ r, and r stands for the length of the character string. Then, this mapping φ : S∗ → S∗ is referred to as an L mapping. Note: From the definition of L mappings, it follows that the set of m(≥ n) production rules from S to S∗: P = {p(1)1 , . . . , p (r1) 1 , p (1) 2 , . . . , p (r2) 2 , . . . , p(1)n , . . . , p(rn)n } (2) can define (r1r2 . . . rn) many L mappings from S to S∗, where n∑ i=1 ri = m. The set of all L mappings determined by the set P is denoted by Φ = {φ1, φ2, . . . , φr1r2...rn}. Proposition 2.1 (Properties of L mappings). For any α, β ∈ S∗ and m,n ∈ Z+, each L mapping φ satisfies the following properties: (i) φ(α) ∈ S∗ is uniquely defined; (ii) If φ|s is surjective S → S, then φ|s must be bijective; Advances in Systems Science and Applications (2013) Vol.13 No.2 103 (iii) If α = sk1sk2 . . . skp ∈ S∗, then φ(α) = φ(sk1)φ(sk2) . . . φ(skp); (iv) φ(α⊕ β) = φ(α)⊕ φ(β); (v) φ(mα) = mφ(α); (vi) ∀φ, ϕ ∈ Φ, φϕ(mα⊕ nβ) = mφϕ(α)⊕ nφϕ(β); Proof. Because both (i) and (ii) are evident, it suffices to show (iii) - (vi). (iii) For any α = sk1sk2 . . . skp ∈ S∗, the definition of the L mappings implies that φ(sk1sk2 . . . skp) = pk1(sk1)pk2(sk2) . . . pkp(skp) (3) And, ∀ski ∈ S∗(1 ≤ i ≤ p), we have φ(ski) = p(ski) (4) Hence, φ(α) = φ(sk1sk2 . . . skp) = pk1(sk1)pk2(sk2) . . . pkp(skp) = φ(sk1)φ(sk2) . . . φ(skp). (iv) For any α, β ∈ S∗, from the addition operation on S∗ and property (iii), it follows that φ(α⊕ β) = φ(αβ) = φ(α)φ(β) = φ(α)⊕ φ(β) (5) (v) For any α ∈ S∗ and m ∈ Z+, from the definition of scalar multiplication on S∗ and property (ii), it following that φ(mα) = φ(αα...α︸ ︷︷ ︸ m times ) = φ(α)φ(α)...φ(α)︸ ︷︷ ︸ m times = mφ(α) (6) (vi) For any φ, ϕ ∈ Φ, by employing properties (iv) and (v), we obtain: φϕ(mα⊕ nβ) = φ(mϕ(α)⊕ nϕ(β)) = mφϕ(α)⊕ nφϕ(β) (7) QED. 2.2 Simple L-Systems With the concept of L-mappings in place, let us now look at how to define simple L-systems. According to the classification of simple L systems, deterministic and random simple L systems, we now establish the relevant definitions by using the concept of L mappings. Definition 2.4(Deterministic simple L systems). Let S = {s1, s2, ..., sn} be a finite set of characters and S∗ the set of all strings of characters from S. Assume that φ : S∗ → S∗ is a given L mapping. For any given initial string ω ∈ S∗, the system that is made up of the nth iterations φn(ω), n ≥ 1, is referred to a deterministic simple L (D0L) system (of order n), denoted by the ordered triplet ⟨S, ω, φ⟩. Definition 2.5(Random simple L systems). Let S and S∗ be the same as in 104 Xiaojun Duan:Set-Theoretic Design and Analysis of L Systems Definition 2.4, Φ = {φ1, φ2, ..., φk} a set of k L mappings from S∗ to S∗, and ξ the L mapping randomly drawn from Φ such that the probability P (ξ = φi) for ξ to be φi is πi, where k∑ i=1 πi = 1. For a given initial string of characters ω ∈ S∗ , the system that is made up of the nth generalized iterations ξnξn−1...ξ1(ω), the composite of the mappings ξ1, ..., ξn−1, ξn, n ≥ 1, is referred to as a random simple L (R0L) system (of order n), where ξ1, ξ2, ..., ξn are independent and i- dentical distributions. This system is written as the following ordered quadruple ⟨S, ω,Φ, π⟩. 3 Properties of Simple L Systems From the definitions, it follows that each simple L system is produced by iterations or generalized iterations of L mappings. Hence, the properties of simple L systems are determined by those of L mappings. Theorem 3.1(Property of linearity). Each simple L system is a linear system. Proof. Assume that the deterministic nth order simple L system is given as L1 = ⟨S, ω, φ⟩, and the random nth order simple L system L2 = ⟨S, ω,Φ, π⟩, where n ≥ 1. To show both L1 and L2 are linear systems, it suffices to show that both L1 and L2 systems respectively satisfy the superposition principle. (I)We use mathematical induction to prove that φn satisfies the superposition principle. When n = 1, ∀α, β ∈ S∗, k1, k2 ∈ Z+, properties (iv) and (v) of L-mappings imply that φ(k1α⊕ k2β) = k1φ(α)⊕ k1φ(β) (7) So, φ satisfies the superposition principle. Assume that when n = k, k ≥ 1,φk satisfies the superposition principle. That is, ∀α, β ∈ S∗, k1, k2 ∈ Z+, the following holds true: φk(k1α⊕ k2β) = k1φ k(α)⊕ k2φ k(β) (8) then when n = k + 1 , we have φk+1(k1α⊕ k2β) = φ(φk(k1α⊕ k2β)) = φ(k1φ k(α)⊕ k2φ k(β)) = k1φ k+1(α)⊕ k2φ k+1(β) (9) Hence, ∀n ≥ 1, φn satisfies the superposition principle. (II)We show that ξnξn−1...ξ1 satisfies the superposition principle. From the definition of random simple L systems, it follows that ξi , 1 ≤ i ≤ n, stands for the L mapping φj , 1 ≤ j ≤ N , where N is the total number of elements in the set Φ , randomly selected from Φ at step i. Because each φi ∈ Φ , 1 ≤ i ≤ N , satisfies the superposition principle, from Advances in Systems Science and Applications (2013) Vol.13 No.2 105 property (vi) of L mappings, it follows that ξnξn−1...ξ1 satisfies the superposition principle. QED. From Theorem 3.1 it follows that in terms of a simple L system, when its order n is relatively large, to shorten the computational time, one can decompose relatively long strings of characters into sums of several shorter strings, which can be handled using parallel treatments to obtain the state of the next moment. Theorem 3.2 (Property of fixed points). The restriction of the L mapping φ in a D0L system on S is bijective from S to S, if and only if for any α ∈ S∗, there is a natural number k such that φk(α) = α. Before proving this result, let us first look at the following lemma. Lemma 3.1 If the restriction of the L mapping φ on S is a bijection from S to S , then ∀si ∈ S , ∃ki ∈ Z+ such that φki(si) = si , 1 ≤ i ≤ n. Proof. By contradiction, assume that ∃s ∈ S, ∀k ∈ Z+ , φk(s) ̸= s. Then let si1 = φ(s), si2 = φ2(s), ..., sin = φn(s) So we have s ̸= si1 , s ̸= si2 , ..., s ̸= sin (10) Step 1: From the first (n − 1) inequalities in equ. (10) and that fact that φ|S : S → S is bijective, it follows that φ(s) ̸= φ(si1), φ(s) ̸= φ(si2), ..., φ(s) ̸= φ(sin−1). That is, si1 ̸= si2 , si1 ̸= si3 , ..., si1 ̸= sin (11) Step 2: From the first (n − 2) inequalities in equ. (11) and that fact that φ|S : S → S is bijective, it follows that φ(si1) ̸= φ(si2), φ(si1) ̸= φ(si3), ..., φ(si1) ̸= φ(sin−1). That is, si2 ̸= si3 , si2 ̸= si4 , ..., si2 ̸= sin (12) By continuing this procedure, we obtain at step (n− 1) that sin−1 ̸= sin (13) Therefore, s ̸= si1 ̸= si2 ̸= ... ̸= sin . It means that there are n + 1 different elements in the set S. However, S has only n elements. A contradiction. So, the assumption that ∃s ∈ S, ∀k ∈ Z+, φk(s) ̸= s does not hold true. In other words, ∀si ∈ S , ∃ki ∈ Z+ such that φki(si) = si , 1 ≤ i ≤ n. QED. In the following, let us prove Theorem 3.2. (⇒)For α = sm1sm2 ...smp ∈ S∗, from Lemma 3.1, it follows that ∀smi ∈ S, ∃ki ∈ Z+, φki(smi) = smi ,1 ≤ i ≤ p . Let k =< k1, k2, ..., kp >. So, φk(α) = φk(sm1sm2 ...smp) = φk(sm1)φ k(sm2)...φ k(smp) = φk1(sm1)φ k2(sm2)...φ kp(smp) = α 106 Xiaojun Duan:Set-Theoretic Design and Analysis of L Systems So, there is a natural number k such that φk(α) = α . (⇐)If ∀α ∈ S∗, there is natural number k such that φk(α) = α, let us take α = s1, s2, . . . , sn. Then ∃k1, k2, ..., kn such that φk1(s1) = s1, φ k2(s2) = s2, ..., φ kn(sn) = sn (14) According to property (ii) of L mappings, to show the restriction of φ on S is a bijection from S to S, it suffice to prove that φ|S : S → S is surjective. Again, we prove this end by contradiction. Assume that ∃s ∈ S , ∀si ∈ S, 1 ≤ i ≤ n ,φ(si) ̸= s . Then we have that ∀k ≥ 1 , φk(s) ̸= s , which contradicts with equ. (14). So, φ|S : S → S is surjective. Hence, φ|S : S → S is bijective. QED. From Theorem 3.2, it follows that in terms of D0L systems, if the restriction φ|S : S → S of L-mapping φ is a bijection, then there are at most k =< k1, k2, ..., kp > different states. Therefore, to produce complicated fractal figures using D0L systems, one should avoid using any such L mapping whose restriction on S is a bijection from S to S. Theorem 3.3(Property of fixed points). The restriction of the L mapping φ in a R0L system on S is a bijection from S to S, if and only if for any α ∈ S∗ , there is a natural number k such that φk(α) = α. Proof. Although as a R0L system, the probability of different mappings at each step is different, the maximum number n of total states of each step is fixed. Since the length p of the mapping is finite, the number of overall states is k = np at most. So there exists a integer k = np to satisfy φk(α) = α. Other parts of the proof are similar to those of Theorem 3.2 and omitted. QED. Remark:In terms of numbers, the finite states of ROL are more than those of DOL. However, from Theorem 3.3, to follows that in order to produce complicated fractal figures using R0L systems, one should still avoid using any such L mapping that its restriction on S is a bijection from S to S. 4 An Explanation of Holistic Emergence of Systems Using DOL Although the mechanism for a simple L system appears is quite straightforward, it clearly shows the attribute of holistic emergence of systems. So, simple L sys- tems can be employed as an effective tool to illustrate the emergence of systems’ wholeness. In the following, we will design a simple binary system to explain the emergence of systems’ wholeness. In the Cartesian coordinate system R2, assume that the initial location of par- ticle A is (0,0) and its initial angle is 0. Let F stand for moving forward one unit step 1, and + turning an angle of π/3 counterclockwise. Now, let us construct the following D0L system L2 = ⟨S, ω, φ⟩, where S = {F,+},ω = F , and φ = { F → F ++F ++F + → + Advances in Systems Science and Applications (2013) Vol.13 No.2 107 The first iteration φ(ω) produces: F++F++F; the second iteration φ2(ω) leads to: F++F++F ++ F++F++F ++ F++F++F; . . .; when the nth order, n ≥ 1 , L system L2 is applied on the particle A, one can obtain the output state as shown in Fig.1. As shown in Fig.1, such an nth order L system, a binary sys- Fig.1 The output state of the L2 system tem, is very simple. Its function can be comprehended as follows: Drive particle A from the starting point at (0,0) to make 3n−1 counterclockwise turns along the triangular trajectory. Now, let us employ this simple binary system to illustrate the emergence of systems’ wholeness: (1) The whole is greater than the sum of its parts; and (2) The function of the whole is more than the sum of the functions of the parts. For our purpose, by the word “sum”, it means the collected pile of parts without any interactions between the parts. As for the word “function”, it is understood as follows: As long as a system is identified, its functionality is a physical ex- istence; however, any function of the system has to be manifested through the system’s act on a specific object that is external to the system. So, to investi- gate the overall function of a system and the sum of the functions of its parts, one needs to consider the respective effects of the system as a whole and each of its parts on an external object. Through analyzing their effects on this object, one can compare the overall effect of the system and the aggregated effect of the parts. Before we illustrate the emergence of the system’s wholeness, let us first estab- lish the following assumptions: (a) The whole can always be divided into several distinguishable parts in terms of components, attributes, or functionalities; (b) Similar parts of the system (or parts with similar attributes) satisfy the 108 Xiaojun Duan:Set-Theoretic Design and Analysis of L Systems additive property, while different parts (or parts with different attributes) do not comply with this property. Here, the additivity stands for the algebraic additivity and is different of the meaning of the “sum” in “the sum of parts”; and (c) When studying the sum of parts’ functionalities, if an identified part does not have any function, then the functionality of this part is seen as “0”. Illustration 1: The whole is greater than the sum of its parts Let us symbolically denote the constructed nth order simple L system L2 = ⟨S, ω, φ⟩, n ≥ 1 , as φn(F ), and sum of parts as ∑ i Si , where Si , i = 1, 2, ..., stands for a division of the whole φn(F ), including all characters. In the follow- ing, we will discuss from two different angles according to the following different divisions of the whole. (1) The whole is greater than the sum of all the elements (The whole is divided using components). If we treat the system L2 as one containing only two components (operations) F and +, then in the nth order L2 system, there are 3n components F and 2(3n -1) components +. From the basic assumptions, it follows that F and + respectively satisfy the additive property. Their algebraic sums are respectively written as S1 = 3n(F ) and S2 = 2(3n − 1)(+) . Then, the sum of the elements of the L2 system can be expressed as 2∑ i=1 Si = S1S2 or 2∑ i=1 Si = S2S1. Applying the output of the elements’ sum 2∑ i=1 Si on the particle A produces a line segment of length 3n , while applying the output of the whole φn(F ) on the particle A creates a regular triangle with each side’s length 1. The whole consti- tutes a figure of the 2-dimensional space, possessing a special structure, while the sum of the elements represents a line segment of the 1-dimensional space without any qualitative mutation. That is to say, the whole has a spatial structural effect that is not shared by the sum of the parts, therefore, φn(F ) > 2∑ i=1 Si . (2) The whole is greater than the sum of its parts, where the whole is divided using attributes. Let us treat the L2 system as being composed of 3n unit vectors of the plane: i⃗1, i⃗2, ..., i⃗3n . That is, we see the vectors i⃗1, i⃗2, ..., i⃗3n as having the same at- tributes. Then this L2 system is made up only of these 3n components of the same attributes. Now, we desire to show φn(F ) > 3n∑ k=1 i⃗k . Evidently, 3n∑ k=1 i⃗k = 0. So, when the output of the sum 3n∑ k=1 i⃗k of the parts is Advances in Systems Science and Applications (2013) Vol.13 No.2 109 applied on the particle A, it is like that no operation is ever applied on A so that the particle A is fastened at the origin without moving. Because the output of the whole φn(F ) is a string of characters, which is equivalent to a sequence of opera- tions with a before and after order, when φn(F ) is applied on the particle A, this particle will repeatedly travel counterclockwise along the triangle and eventually return to the origin. That is to say, the whole possesses a structural effect of time that is not shared by the sum of the parts, therefore, we have φn(F ) > 3n∑ k=1 i⃗k . In fact, the essential difference between the whole and the sum of parts is that the whole has some structural effect in terms of space or time, while the sum of parts does not have. For instance, when N bricks are used to build a house, the whole stands for a building along with the spatial structure of rooms, etc. However, when the components of this building are divided, because there is only one kind of component, the bricks, the sum of the parts satisfies the algebraic additivity and is equal to the N bricks, which do not have the spatial structure of the house. Illustration 2: The functionality of the whole is greater than the sum of parts’ functionalities. Let us first introduce a new kind of set [S], where each element is allowed to appear more than once. To avoid creating any conflict with the conventional set theory, we will only apply the operation of drawing elements out of the set [S] with the following convention: If a non-empty set [S] contains element s at least twice, then drawing one s from [S] means that we take any of the elements s’s. For example, [S] = {a, a, b, a, b} . Then, drawing an a from [S] means that we take any one of the elements a’s. For the nth order simple L2 system, n ≥ 1 , the individual characters (opera- tions) F and + stand for the smallest units of functionalities. Divide this system into (3n+1−2) parts, which include 3n functional units F and 2( 3n-1) functional units +. The set of these (3n+1-2 ) functional units is written as set [S] . We first consider the effect of the whole on the particle A. The function of this L2 system is to order the elements of [S] according to some specific rules. Then, the effect of the system on A is force the particle A to counterclockwisely travel along the triangle 3n−1 times. Now, let us look at the effect on A of each part. When the set [S] is given, the sum of the parts’ functions can be understood as follows: There are a total of m operations, each of which takes mi arbitrary elements from [S] without replace- ment to act on A, until all the elements in [S] are exhausted. Evidently, as long as the order of the elements taking out of the set [S] is different from that of φn(F ) , the total effect of these elements that are individually taken out of [S] will not reach that of the L2 system. Therefore, the whole possesses a functionality the sum of the parts does not share. That is, the function of the whole is greater 110 Xiaojun Duan:Set-Theoretic Design and Analysis of L Systems than the sum of the parts’ functions. In fact, the essential difference between the function of the whole and the sum of parts’ functions is that the whole has an organizational effect, while the sum of the parts does not have. 5 The Design of Simple L Systems 5.1 The Basic Graph Generation Principle of Simple L Systems In essence each L system is a system that rewrites strings of characters. Its working principle is quite simple. If each character is seen as an operation and different characters are seen as distinct operations, then strings of characters can be employed to generate various fractal figures. That is, as long as strings of characters can be generated, one is able to produce figures. The character strings of L systems that are used to generate figures can be made up of any recognizable symbols. For example, in the design of programs, the symbols F, -, and + can be used respectively so that “F” means move one unit length forward from the current location and draw a segment, “-” stands for turning clockwise from the current direction a pre-determined angle, and “+” turning counterclockwise from the current direction another pre-determined angle. When generating character strings, start from an initial string and replace the characters of this string by substrings of characters according to the pre- determined rules. That completes the first iteration. Then, treat the resultant character string from the first iteration as the mother string and replace each character in this string by strings determined by the rules. By continuing this procedure, one can finish the required iterations of an L system, where the length of the resultant string is controlled by the number of iterations. 5.2 A Fractal Structure Design Based on D0L In terms of a tree, it stands for a fractal structure. In particular, each trunk car- ries a large amount of branches, and each branch has an end point, representing a figure with one staring point and many ending points. This fact implies that when one draws a branch to its end, he has to return his drawing pen to draw other structures. Let us take the following conventions: “F” stands for moving forward a unit length 1, and “+” turning an angle of π/8 clockwisely, “-” turning an angle of π/8 counterclockwisely, and the characters within “[ ]” represent a branch; when the characters within a pair of [ ] are implemented, return to the position right before “[” and maintain the original direction, and then carry out the characters after “]”. Assume that the starting point is at (0,0) on the complex plane and the initial direction at π/2 . Now, we design a D0L system G1 = ⟨S1, ω1, φ1⟩ as follows: S1 = {F,+,−, [, ]}; ω1 = F ;and Advances in Systems Science and Applications (2013) Vol.13 No.2 111 Fig.2 The fractal structures: a tree dancing in breeze (of different iteration steps) Fig.3 The fractal structures: a standing tree (n = 5, α = π/8, with design form F→FF+[+F[−FF−]−F]− [−F[−FF+]F]) 112 Xiaojun Duan:Set-Theoretic Design and Analysis of L Systems φ1 =  F → FF + [+F− F− F]− [− F + F + F] + → + − → − [ → [ ] → ] Then, we can produce the fractal structures as shown in Fig.2. We can obtain other illustrations by just changing the design forms as Fig.3-5. Fig.4 The fractal structures: a tree towards sun (n = 5, α = π/8, with design form F→FF+[+F[−F−F]−F]− [−F[F−FF+F]F]) Fig.5 The fractal structures: a floating grass ball (n = 4, α = π/8, with design form F →FF+[[+F−FF−F]− [−F+FF+F]] ) 5.3 A Fractal Structure Design Based on R0L Systems In nature, the forms plants take are not invariant. Even for the same kinds of plants, their shapes can vary from one plant to another. Such varieties are caused Advances in Systems Science and Applications (2013) Vol.13 No.2 113 by the effects of the environment. Fig.6 The different fractal structures for a R0L system with each iteration un- changed (n = 4, α = π/16 ) In terms of the simulation effects of plants, the figures created by using D0L systems seem to be quite stiff. Under the prerequisite of maintaining the main characteristics of plants, in order to generate varieties on the details, we can utilize the plants? structures produced out of R0L systems. The advantage of these figures is that these simulated plants are more real-life like and much closer to the true forms of natural plants. To this end, let us design a R0L system G2 = ⟨S1, ω1,Φ, π⟩ as follows: S1 = {F,+,−, [, ]}; ω1 = F ; Φ = {φ1, φ2, φ3}; where φ1 =  F → F[+F]F[− F]F + → + − → − [ → [ ] → ] ,φ2 =  F → F[+F]F[− F[+F]] + → + − → − [ → [ ] → ] , 114 Xiaojun Duan:Set-Theoretic Design and Analysis of L Systems φ3 =  F → FF[− F + F + F] + [+F− F− F] + → + − → − [ → [ ] → ] and π = P (ξ = φi) = 1/3, i = 1, 2, 3 . Then the fractal structures can be produced. For instance, Fig.6 shows the different fractal structures of a R0L system with each iteration unchanged. Fig.7 shows the different fractal structures of a R0L system where each iteration is different. Fig.7 The different fractal structures of a R0L system with each iteration different (n = 5, α = π/16 ) 6 Summary Although the design principle underlying the L systems is quite straightforward, these systems can be employed to produce many complicated fractal pattern- s. After many years of research, L systems have evolved from the original rewrite systems of characters to such capable systems that can describe com- plex 3-dimensional systems. They have evolved from the simplest D0L systems to random L systems, and then to open L systems. The L systems have provid- ed simulations of fractal structures that have become over time much closer to real-life like, and have been employed as an important tool for creating virtual plants. From the point of view of set theory, this paper first establishes a rigorous mathematical definition of simple L-system, and then proves the common char- acteristics of simple L-systems. By doing so, this paper developed the badly needed fundamental ground for further investigation of L systems. It is expected to be applicable to form the theoretical framework of other L systems. Acknowledgements Advances in Systems Science and Applications (2013) Vol.13 No.2 115 This work is supported by the Natural Science Foundation of China (60974124), the Program for New Century Excellent Talents in University and the Project- sponsored by SRF for ROCS, SEM in China. References [1] Lindenmayer, A. (1968), “Mathematical models for cellular interaction in development”, Journal of Theoretical Biology, Vol.18, pp.280-289. [2] Prusinkiewicz, P, Lindenmayer, A. (1996), The Algorithmic Beauty of Plants, London: Springer. [3] Eichhorst, P, Savitch, W. J. (1980), “Growth functions of stochastic Linden- mayer systems”, Information and Control, Vol.45, pp.217-228. [4] Herman, G.T, Rozenberg, G. (1975), Developmental Systems and Languages, Amsterdam: North-Holland Publishing Company. [5] Prusinkiewicz, P, Hammel, M, Mjolsness, E. (1993), “Animation of plant developmen”, Acm Siggraph, pp.351-360. [6] Lin, Y. (1999), “General systems theory: a mathematical approach”, New York: Kluwer Academic and Plenum Publishers. Corresponding Author Xiaojun Duan can be contracted at: xjduan@nudt.edu.cn