L-systems

The theory of $ L $- systems originated from the work of A. Lindenmayer, [a1]. The original aim of this theory was to provide mathematical models for the development of simple filamentous organisms. At the beginning, $ L $- systems were defined as linear arrays of finite automata; later, however, they were reformulated into the more suitable framework of grammar-like constructs. From then on, the theory of $ L $- systems was developed essentially as a branch of formal language theory (cf. Formal languages and automata).

The essential feature about $ L $- systems, as opposed to grammars, is that the rewriting of a string happens in a parallel manner, contrary to the sequential rewriting in grammars. This means that at every step of the rewriting process according to an $ L $- system every letter has to be rewritten. One step of the rewriting process according to a grammar changes only some part of the string considered.

Consider a very simple example. Assume that one is dealing with a context-free grammar (cf. Grammar, context-free) containing the production $ S \rightarrow SS $. Then, starting from $ S $, one obtains any string of the form $ S ^ {n} $, where $ n \geq 1 $. This follows because at one step of the rewriting process one can replace one occurrence of $ S $ by $ SS $ and leave the other occurrences unchanged. Assume next that one is dealing with an $ L $- system containing the production $ S \rightarrow SS $. Then, starting from $ S $, one obtains by this production only strings of the form $ S ^ {2 ^ {n} } $, $ n \geq 0 $. This follows because one cannot leave occurrences of $ S $ unchanged. Thus, if one is rewriting the string $ SS $, one obtains at one step the string $ SSSS = S ^ {4} $, and not the string $ S ^ {3} $. On the other hand, if this $ L $- system contains also the production $ S \rightarrow S $, then one can derive any string of the form $ S ^ {n} $, $ n \geq 1 $.

This parallelism in rewriting reflects the basic biological motivation behind $ L $- systems. One is trying to model the development of an organism. The development takes place in a parallel way, simultaneously everywhere in the organism. Sequential rewriting is not suitable for this modeling.

The simplest version of $ L $- systems assumes that the development of a cell is free of influence of other cells. This type of $ L $- systems is customarily called an $ OL $- system ( "O" stands for zero-sided communication between cells). By definition, an $ OL $- system is a triple $ G = ( \Sigma , P, \omega ) $, where $ \Sigma $ is an alphabet, $ \omega $ is a word over $ \Sigma $ and $ P $ is a finite set of rewriting rules of the form

$$ a \rightarrow x,\ \ a \in \Sigma ,\ \ x \in \Sigma ^ {*} . $$

(It is also assumed that $ P $ contains at least one rule for each letter of $ \Sigma $.) The language of $ G $ consists of all words which can be derived from $ \omega $ using rules of $ P $ in the parallel way.

As an example, consider the $ OL $- system

$$ ( \{ a, b \} , a, \{ a \rightarrow b, b \rightarrow ab \} ). $$

The first few words in the generated language are

$$ a, b, ab, bab, abbab, bababbab, abbabbababbab. $$

Since the system is deterministic (there is only one production for each letter), its language is generated as a sequence in a unique way. (Deterministic systems are denoted by the letter $ D $.) Notice that the lengths of the words in this sequence form the famous Fibonacci sequence (cf. Fibonacci word). In fact, this $ OL $- system provides a very simple way to generate the Fibonacci sequence, when compared to other possible devices in automata and formal language theory. The system is also propagating (abbreviated $ P $): there are no erasing productions, where a letter goes to the empty word $ \lambda $.

In $ L $- systems with interactions, abbreviated $ IL $- systems, the productions have the form $ ( y, a, z) \rightarrow x $. Such a production can be applied to rewrite the letter $ a $ in the context $ yaz $ as $ x $. If in all productions the length of $ y $( respectively, $ z $) equals $ k $( respectively, $ l $), one speaks of a system with $ \langle k, l\rangle $ interactions. (From the biological point of view, this means that an individual cell may communicate with $ k $ of its left and $ l $ of its right neighbours.) Near the ends of the string, the missing neighbours are provided by a special letter $ g $. For instance, the string $ aaa $ may be rewritten as $ bbaba $ by the $ ( 1, 1) $ productions $ ( g, a, a) \rightarrow bb $, $ ( a, a, a) \rightarrow ab $, $ ( a, a, g) \rightarrow a $.

An $ L $- system with tables (abbreviated $ T $) has several sets of rewriting rules instead of just one set. At one step of the rewriting process, rules belonging to the same set have to be applied. For an $ L $- system of any type, systems of the same type and with tables may be considered. The biological motivation for introducing tables is that one may want different rules to take care of different environmental conditions (heat, light, etc.) or of different stages of development.

When defining the language generated by an $ L $- system, so far only the exhaustive approach has been considered: all words derivable from the axiom by the rules in a parallel way belong to the language. The families of languages obtained in this fashion (for instance, the family of $ OL $- languages, also simply denoted by $ OL $) have very weak closure properties. In addition to the exhaustive approach, various selective approaches are possible.

The terminal alphabet provides a filtering mechanism: Words generated by the system have to pass through this filter in order to qualify to be included in the language. In the next definition one again uses an abbreviation customary in the theory of $ L $- systems: the letter $ E $ means extended.

An $ EOL $- system is a pair $ G _ {1} = ( G, \Sigma _ {T} ) $, where $ G = ( \Sigma , P, w) $ is an $ OL $- system and $ \Sigma _ {T} $ is a subset of $ \Sigma $, referred to as the terminal alphabet. The language generated by $ G _ {1} $ is defined by

$$ L ( G _ {1} ) = L ( G) \cap \Sigma _ {T} ^ {*} . $$

Languages of this form are called $ EOL $- languages.

Given a context-free grammar $ G $, for each letter $ \alpha $( both terminal and non-terminal) one adds the production $ \alpha \rightarrow \alpha $ and views the resulting construct $ G _ {1} $ as an $ EOL $- system. It is then clear that $ L ( G) = L ( G _ {1} ) $. This shows that every context-free language is also an $ EOL $- language. The next example demonstrates how to generate a non-context-free language by an $ EOL $- system.

Consider the $ EOL $- system $ G $ with the axiom $ S $ and productions $ S \rightarrow ABC $, $ A \rightarrow A \overline{A}\; $, $ B \rightarrow B \overline{B}\; $, $ C \rightarrow C \overline{C}\; $, $ \overline{A}\; \rightarrow \overline{A}\; $, $ \overline{B}\; \rightarrow \overline{B}\; $, $ \overline{C}\; \rightarrow \overline{C}\; $, $ \overline{A}\; \rightarrow a $, $ \overline{B}\; \rightarrow b $, $ \overline{C}\; \rightarrow c $, $ A \rightarrow a $, $ B \rightarrow b $, $ C \rightarrow c $, $ a \rightarrow N $, $ b \rightarrow N $, $ c \rightarrow N $, and $ N \rightarrow N $, were $ \{ a, b, c \} $ is the terminal alphabet. It is not difficult to verify that

$$ L ( G) = \{ {a ^ {n} b ^ {n} c ^ {n} } : {n \geq 1 } \} . $$

The system $ G $ is based on the synchronization of terminals: the terminals have to be introduced simultaneously in the whole word. If terminals are introduced only in some parts of the word, then the derivation cannot be continued to yield a word over the terminal alphabet. This is due to the fact that terminals give rise only to the "garbage" letter $ N $, which cannot be eliminated once it is introduced.

In the same way, one may speak of $ EIL $- systems and $ EIL $- languages as well. A language is recursively enumerable if and only if it is an $ EIL $- language.

An area quite essential in the study of $ L $- systems is the theory of growth functions. From the biological point of view, the growth function measures the size of the organism modelled. From the theoretical point of view, the theory of growth functions reflects a fundamental aspect of $ L $- systems: generated languages as sequences of words.

To a $ DOL $- system $ G $ one associates the function $ f _ {G} $ mapping the set of non-negative integers into itself as follows. For $ i \geq 0 $, the value $ f _ {G} ( i) $ is defined to be the length of the $ i $- th word in the sequence of $ G $. The function $ f _ {G} $ is called the growth function of $ G $.

For instance, for the $ DOL $- system $ G $ with the axiom $ a $ and the only production $ a \rightarrow aa $, one has $ f _ {G} ( i) = 2 ^ {i} $ for all $ i \geq 0 $.

For the $ DOL $- system $ G $ with the axiom $ a $ and the productions $ a \rightarrow ab $ and $ b \rightarrow b $, one has $ f _ {G} ( i) = i + 1 $ for all $ i \geq 0 $.

For the $ DOL $- system $ G $ with the axiom $ a $ and productions $ a \rightarrow abc ^ {2} $, $ b \rightarrow bc ^ {2} $ and $ c \rightarrow c $( respectively, $ a \rightarrow abd ^ {6} $, $ b \rightarrow bcd ^ {11} $, $ c \rightarrow cd ^ {6} $, and $ d \rightarrow d $) one has $ f _ {G} ( i) = ( i + 1) ^ {2} $( respectively, $ f _ {G} ( i) = ( i + 1) ^ {3} $).

The analysis problem for growth functions consists of determining the growth function of a given $ DOL $- system. The synthesis problem consists of materializing given functions — if possible — as $ DOL $ growth functions.

To a given $ DOL $- system $ G $ with alphabet $ \{ a _ {1} \dots a _ {n} \} $ one associates the axiom vector $ \pi _ {G} = ( v _ {1} \dots v _ {n} ) $, where $ v _ {i} $ equals the number of occurrences of $ a _ {i} $ in the axiom of $ G $ for each $ i = 1 \dots n $. One also associates with $ G $ the $ ( n \times n) $ growth matrix $ M _ {G} $ whose $ ( i, j) $- th entry equals the number of occurrences of $ a _ {j} $ in the production for $ a _ {i} $ for all $ i $ and $ j $. Finally, $ \eta $ is a column vector of dimension $ n $ consisting entirely of 1's.

The growth function $ f _ {G} $ associated to a $ DOL $- system $ G $ satisfies

$$ f _ {G} ( i) = \pi _ {G} M _ {G} ^ {i} \eta \ \ \textrm{ for } \textrm{ all } i \geq 0. $$

Consequently, a growth function of a $ DOL $- system cannot grow faster than exponentially, and if it is ultimately growing, it cannot grow slower than linearly. The growth functions of $ IL $- systems, analogously defined, do not necessarily satisfy these conditions.

More recently, a graph-theoretical framework for $ L $- systems has proved to provide a more unified approach to $ 1 $- dimensional as well as $ 2 $- or $ 3 $- dimensional cellular development. This graph interpretation is also topological, i.e. it concerns the neighbourhood relationships among cells. To these systems analytical and graphical geometric specifications can be added for lengths, angles, colours, and other properties of cells or their walls and edges. The most useful of these graph-theoretical constructs have been those in which edge labels are the main control elements. In the course of applying these constructs one can make use of many of the results obtained by formal-language-theoretic means.

References

[a1]	A. Lindenmayer, "Mathematical models for cellular interaction in development I-II" J. Theoret. Biology , 18 (1968) pp. 280–315
[a2]	G. Rozenberg, A. Salomaa, "The mathematical theory of L-systems" , Acad. Press (1980)
[a3]	A. Lindenmayer, "Models for multicellular development: characterization, inference and complexity of L-systems" A. Kelemenovà (ed.) J. Kelemen (ed.) , Trends, Techniques, and Problems in Theoretical Computer Science: 4th internat. meeting young computer scientists, Smolenice, Oct. 1986 , Lect. notes in comp. science , 281 , Springer (1987) pp. 138–168