Namespaces
Variants
Actions

Difference between revisions of "L-systems"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (link)
m (tex encoded by computer)
Line 1: Line 1:
The theory of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l0570502.png" />-systems originated from the work of A. Lindenmayer, [[#References|[a1]]]. The original aim of this theory was to provide mathematical models for the development of simple filamentous organisms. At the beginning, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l0570503.png" />-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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l0570504.png" />-systems was developed essentially as a branch of formal language theory (cf. [[Formal languages and automata|Formal languages and automata]]).
+
<!--
 +
l0570502.png
 +
$#A+1 = 185 n = 2
 +
$#C+1 = 185 : ~/encyclopedia/old_files/data/L057/L.0507050 \BMI L\EMI\AAhsystems
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
The essential feature about <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l0570505.png" />-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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l0570506.png" />-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.
+
{{TEX|auto}}
 +
{{TEX|done}}
  
Consider a very simple example. Assume that one is dealing with a context-free grammar (cf. [[Grammar, context-free|Grammar, context-free]]) containing the production <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l0570507.png" />. Then, starting from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l0570508.png" />, one obtains any string of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l0570509.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705010.png" />. This follows because at one step of the rewriting process one can replace one occurrence of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705011.png" /> by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705012.png" /> and leave the other occurrences unchanged. Assume next that one is dealing with an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705013.png" />-system containing the production <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705014.png" />. Then, starting from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705015.png" />, one obtains by this production only strings of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705016.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705017.png" />. This follows because one cannot leave occurrences of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705018.png" /> unchanged. Thus, if one is rewriting the string <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705019.png" />, one obtains at one step the string <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705020.png" />, and not the string <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705021.png" />. On the other hand, if this <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705022.png" />-system contains also the production <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705023.png" />, then one can derive any string of the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705024.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705025.png" />.
+
The theory of  $  L $-
 +
systems originated from the work of A. Lindenmayer, [[#References|[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|Formal languages and automata]]).
  
This parallelism in rewriting reflects the basic biological motivation behind <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705026.png" />-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 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.
  
The simplest version of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705027.png" />-systems assumes that the development of a cell is free of influence of other cells. This type of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705028.png" />-systems is customarily called an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705030.png" />-system ( "O" stands for zero-sided communication between cells). By definition, an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705031.png" />-system is a triple <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705032.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705033.png" /> is an alphabet, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705034.png" /> is a word over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705035.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705036.png" /> is a finite set of rewriting rules of the form
+
Consider a very simple example. Assume that one is dealing with a context-free grammar (cf. [[Grammar, context-free|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 $.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705037.png" /></td> </tr></table>
+
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.
  
(It is also assumed that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705038.png" /> contains at least one rule for each letter of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705039.png" />.) The language of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705040.png" /> consists of all words which can be derived from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705041.png" /> using rules of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705042.png" /> in the parallel way.
+
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
  
As an example, consider the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705043.png" />-system
+
$$
 +
a  \rightarrow  x,\ \
 +
a \in \Sigma ,\ \
 +
x \in \Sigma  ^ {*} .
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705044.png" /></td> </tr></table>
+
(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
 
The first few words in the generated language are
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705045.png" /></td> </tr></table>
+
$$
 +
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705046.png" />.) Notice that the lengths of the words in this sequence form the famous Fibonacci sequence (cf. [[Fibonacci word]]). In fact, this <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705047.png" />-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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705049.png" />): there are no erasing productions, where a letter goes to the empty word <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705050.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705052.png" />-systems with interactions, abbreviated <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705054.png" />-systems, the productions have the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705055.png" />. Such a production can be applied to rewrite the letter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705056.png" /> in the context <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705057.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705058.png" />. If in all productions the length of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705059.png" /> (respectively, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705060.png" />) equals <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705061.png" /> (respectively, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705062.png" />), one speaks of a system with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705063.png" /> interactions. (From the biological point of view, this means that an individual cell may communicate with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705064.png" /> of its left and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705065.png" /> of its right neighbours.) Near the ends of the string, the missing neighbours are provided by a special letter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705066.png" />. For instance, the string <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705067.png" /> may be rewritten as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705068.png" /> by the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705069.png" /> productions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705070.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705071.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705072.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705074.png" />-system with tables (abbreviated <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705075.png" />) 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705076.png" />-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.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705078.png" />-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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705080.png" />-languages, also simply denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705081.png" />) have very weak closure properties. In addition to the exhaustive approach, various selective approaches are possible.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705082.png" />-systems: the letter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705083.png" /> means extended.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705085.png" />-system is a pair <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705086.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705087.png" /> is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705088.png" />-system and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705089.png" /> is a subset of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705090.png" />, referred to as the terminal alphabet. The language generated by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705093.png" /> is defined by
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705094.png" /></td> </tr></table>
+
$$
 +
L ( G _ {1} )  = L ( G) \cap \Sigma _ {T}  ^ {*} .
 +
$$
  
Languages of this form are called <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705096.png" />-languages.
+
Languages of this form are called $  EOL $-
 +
languages.
  
Given a context-free grammar <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705097.png" />, for each letter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705098.png" /> (both terminal and non-terminal) one adds the production <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l05705099.png" /> and views the resulting construct <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050100.png" /> as an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050101.png" />-system. It is then clear that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050102.png" />. This shows that every context-free language is also an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050103.png" />-language. The next example demonstrates how to generate a non-context-free language by an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050104.png" />-system.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050105.png" />-system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050106.png" /> with the axiom <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050107.png" /> and productions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050108.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050109.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050110.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050111.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050112.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050113.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050114.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050115.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050116.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050117.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050118.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050119.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050120.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050121.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050122.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050123.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050124.png" />, were <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050125.png" /> is the terminal alphabet. It is not difficult to verify that
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050126.png" /></td> </tr></table>
+
$$
 +
L ( G)  = \{ {a  ^ {n} b  ^ {n} c  ^ {n} } : {n \geq  1 } \}
 +
.
 +
$$
  
The system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050127.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050128.png" />, which cannot be eliminated once it is introduced.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050130.png" />-systems and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050132.png" />-languages as well. A language is recursively enumerable if and only if it is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050133.png" />-language.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050134.png" />-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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050135.png" />-systems: generated languages as sequences of words.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050136.png" />-system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050137.png" /> one associates the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050138.png" /> mapping the set of non-negative integers into itself as follows. For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050139.png" />, the value <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050140.png" /> is defined to be the length of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050141.png" />-th word in the sequence of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050142.png" />. The function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050143.png" /> is called the growth function of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050145.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050146.png" />-system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050147.png" /> with the axiom <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050148.png" /> and the only production <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050149.png" />, one has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050150.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050151.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050152.png" />-system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050153.png" /> with the axiom <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050154.png" /> and the productions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050155.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050156.png" />, one has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050157.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050158.png" />.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050159.png" />-system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050160.png" /> with the axiom <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050161.png" /> and productions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050162.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050163.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050164.png" /> (respectively, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050165.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050166.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050167.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050168.png" />) one has <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050169.png" /> (respectively, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050170.png" />).
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050172.png" />-system. The synthesis problem consists of materializing given functions — if possible — as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050174.png" /> growth functions.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050175.png" />-system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050176.png" /> with alphabet <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050177.png" /> one associates the axiom vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050179.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050180.png" /> equals the number of occurrences of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050181.png" /> in the axiom of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050182.png" /> for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050183.png" />. One also associates with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050184.png" /> the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050185.png" /> growth matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050187.png" /> whose <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050188.png" />-th entry equals the number of occurrences of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050189.png" /> in the production for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050190.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050191.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050192.png" />. Finally, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050193.png" /> is a column vector of dimension <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050194.png" /> consisting entirely of 1's.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050195.png" /> associated to a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050196.png" />-system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050197.png" /> satisfies
+
The growth function $  f _ {G} $
 +
associated to a $  DOL $-
 +
system $  G $
 +
satisfies
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050198.png" /></td> </tr></table>
+
$$
 +
f _ {G} ( i)  = \pi _ {G} M _ {G}  ^ {i} \eta \ \
 +
\textrm{ for }  \textrm{ all }  i \geq  0.
 +
$$
  
Consequently, a growth function of a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050199.png" />-system cannot grow faster than exponentially, and if it is ultimately growing, it cannot grow slower than linearly. The growth functions of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050200.png" />-systems, analogously defined, do not necessarily satisfy these conditions.
+
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050201.png" />-systems has proved to provide a more unified approach to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050202.png" />-dimensional as well as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050203.png" />- or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050204.png" />-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.
+
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====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  A. Lindenmayer,  "Mathematical models for cellular interaction in development I-II"  ''J. Theoret. Biology'' , '''18'''  (1968)  pp. 280–315</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  G. Rozenberg,  A. Salomaa,  "The mathematical theory of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050205.png" />-systems" , Acad. Press  (1980)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  A. Lindenmayer,  "Models for multicellular development: characterization, inference and complexity of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050206.png" />-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</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  A. Lindenmayer,  "Mathematical models for cellular interaction in development I-II"  ''J. Theoret. Biology'' , '''18'''  (1968)  pp. 280–315</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  G. Rozenberg,  A. Salomaa,  "The mathematical theory of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050205.png" />-systems" , Acad. Press  (1980)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  A. Lindenmayer,  "Models for multicellular development: characterization, inference and complexity of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l057/l057050/l057050206.png" />-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</TD></TR></table>

Revision as of 22:15, 5 June 2020


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 -systems" , Acad. Press (1980)
[a3] A. Lindenmayer, "Models for multicellular development: characterization, inference and complexity of -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
How to Cite This Entry:
L-systems. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=L-systems&oldid=37194
This article was adapted from an original article by G. RozenbergA. Salomaa (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article