View source for D0L-sequence

[[L-systems|$L$-systems]] were introduced by A. Lindenmayer in the late 1960s to model (in discrete time) the development of filamentous organisms. A fundamental feature of these systems is that in each step each cell (represented by a symbol from a finite [[alphabet]]) has to be rewritten according to the developmental rules of the organism. This parallelism is the main difference between $L$-systems and the classical Chomsky grammars (cf. also [[Grammar, generative]]). In fact, soon after their introduction, $L$-systems constituted a significant part of [[formal language]] theory, allowing one to compare parallel rewriting to a more classical sequential one, see [[#References|[a13]]].

The simplest $L$-system is a so-called D$0$L-system, where the development starts from a single word and continues deterministically step by step in a context independent way, that is, the development of a symbol depends only on that symbol. (Here,  "D"  stands for determinism,  $0$  for zero-sided interaction and  "L"  for Lindenmayer.) Formally, a D$0$L-system is a triple $\mathcal{G} = (\Sigma,h,w)$, where $\Sigma$ is a finite alphabet, $h$ is an [[Endomorphism|endomorphism]] of the [[free monoid]] generated by $\Sigma$, in symbols $\Sigma^*$, and $w$ is a starting word. The system $\mathcal{G}$ defines the D$0$L-sequence
$$
S(\mathcal{G})\ : \ w,\,h(w),\,h^2(w),\,\ldots
$$
the D$0$L-growth sequence
$$
GS(\mathcal{G})\ : \ |w|,\,|h(w)|,\,|h^2(w)|,\,\ldots
$$
where $| \cdot |$ denotes the length of a word, and the D$0$L-language
$$
L(\mathcal{G}) = \{ H^i(w) : i \ge 0 \} \ .
$$

It is not only the mathematical simplicity of the definitions, but rather the challenging mathematical problems connected with these notions, in particular with D$0$L-sequences, which made D$0$L-systems mathematically very fruitful. The most famous problem is the D$0$L-sequence equivalence problem, which asks for an algorithm to decide whether or not two D$0$L-sequences coincide. The impact of this nice problem is discussed in [[#References|[a11]]].

D$0$L-languages emphasize a static nature of the systems and are more related to classical formal language theory. D$0$L-growth sequences, in turn, are closely connected to the theory of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120010/d12001032.png" />-rational [[Formal power series|formal power series]], and in fact allow one to reformulate certain classical problems, such as the algorithmic problem on the existence of a zero in a sequence defined by a linear recurrence, see [[#References|[a15]]]. Finally, D$0$L-sequences represent a dynamical feature of the systems. Moreover, such sequences are defined in a very simple and natural way: by iterating a morphism.

The D$0$L-sequence equivalence problem was first shown to be algorithmically decidable in [[#References|[a4]]] (cf. also [[Proof theory|Proof theory]]). A simpler solution was found in [[#References|[a7]]], and finally a third completely different solution can be based on the validity of the [[Ehrenfeucht conjecture|Ehrenfeucht conjecture]] and Makanin's algorithm for the solvability of word equations over free monoids, as shown in [[#References|[a6]]]. It is interesting to note that only the third solution extends to a multi-dimensional variant of the D$0$L-problem, the so-called DT$0$L-sequence equivalence problem. In the latter problem, the word sequences of (a1) are replaced by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120010/d12001038.png" />-ary trees obtained by iterating <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120010/d12001039.png" /> different morphisms in all possible ways.

Despite the above solutions, an intriguing feature of the D$0$L-sequence equivalence problem remains. Indeed, none of the above solutions is practical. However, it has been conjectured that only the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120010/d12001041.png" /> first elements of the sequences have to be compared in order to decide the equivalence. This <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120010/d12001044.png" />-conjecture is known to hold when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120010/d12001045.png" /> is binary, see [[#References|[a10]]], but no reasonable (even exponential) bound is known (1998) in the general case.

As already hinted at, the major mathematical importance of D$0$L-systems lies in the fact that they (in particular, the research on the D$0$L-sequence equivalence problem) motivated a large amount of fundamental research on morphisms of free monoids. Below a few such examples are given.

Consider a [[morphism]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120010/d12001048.png" /> satisfying <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120010/d12001049.png" /> for some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120010/d12001050.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120010/d12001051.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120010/d12001052.png" /> is non-erasing, i.e. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120010/d12001053.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120010/d12001054.png" />, then there exists a unique infinite word

<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/d/d120/d120010/d12001055.png" /></td> </tr></table>

Consequently, D$0$L-sequences can be used in a very natural way to define infinite words. Implicitly, A. Thue used this approach at the beginning of the 20th century in his seminal work on square- and cube-free infinite words over a finite alphabet, see [[#References|[a16]]]. Since the early 1980s, such a research on non-repetitive words, revitalized by [[#References|[a2]]], has been a central topic in the combinatorics of words. Almost exclusively non-repetitive words are constructed by the above method of iterating a morphism.

The D$0$L-sequence equivalence problem asks whether or not two morphism <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120010/d12001059.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120010/d12001060.png" /> agree on a D$0$L-language defined by one of the morphisms, that is, whether or not <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120010/d12001062.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120010/d12001063.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120010/d12001064.png" />. This has motivated the consideration of so-called equality languages of two morphisms <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120010/d12001065.png" />:

<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/d/d120/d120010/d12001066.png" /></td> </tr></table>

Research on equality languages revealed amazing morphic characterizations of recursively enumerable languages, see [[#References|[a3]]], [[#References|[a8]]] and [[#References|[a14]]]. For example, each recursively enumerable language (cf. also [[Formal languages and automata|Formal languages and automata]]) can be expressed in the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120010/d12001067.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120010/d12001068.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120010/d12001069.png" /> are morphisms and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120010/d12001070.png" /> is a regular language (cf. also [[Grammar, regular|Grammar, regular]]). Furthermore, the fundamental [[Post correspondence problem]] can be formulated as a problem of deciding whether or not <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120010/d12001071.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120010/d12001072.png" /> denotes the unit of the free monoid <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120010/d12001073.png" />.

A third, and apparently the most fundamental, consequence of research on D$0$L-systems was a discovery of a compactness property of free semi-groups: Each system of equations over a free monoid containing a finite number of variables is equivalent to some of its finite subsystems (cf. also [[Free semi-group]]). This property (often referred to as the Ehrenfeucht conjecture) was conjectured by A. Ehrenfeucht in the early 1970s (in a slightly different form) and later established in [[#References|[a1]]] and [[#References|[a9]]].

Finally, it is worth mentioning that besides their mathematical inspiration, D$0$L-sequences have turned out to be useful in areas such as computer graphics and simulation of biological developments, see [[#References|[a5]]] and [[#References|[a12]]].

====References====
<table>
<TR><TD valign="top">[a1]</TD> <TD valign="top">  M. Albert,   J. Lawrence,   "A proof of Ehrenfeucht's conjecture"  ''Theoret. Comput. Sci.'' , '''41'''  (1985)  pp. 121–123</TD></TR>
<TR><TD valign="top">[a2]</TD> <TD valign="top">  J. Bertel,   "Mots sans carré et morphismes itérés"  ''Discrete Math.'' , '''29'''  (1979)  pp. 235–244</TD></TR>
<TR><TD valign="top">[a3]</TD> <TD valign="top">  K. Culik II,   "A purely homomorphic characterization of recursively enumerable sets"  ''J. Assoc. Comput. Mach.'' , '''26'''  (1979)  pp. 345–350</TD></TR>
<TR><TD valign="top">[a4]</TD> <TD valign="top">  K. Culik II,   I. Fris,   "The decidability of the equivalence problem for D0L-systems"  ''Inform. Control'' , '''35'''  (1977)  pp. 20–39</TD></TR>
<TR><TD valign="top">[a5]</TD> <TD valign="top">  K. Culik II,   J. Kari,   "On the power of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d120/d120010/d12001076.png" />-systems in image generation"  G. Rozenberg (ed.)  A. Salomaa (ed.) , ''Developments in Language Theory'' , World Sci.  (1994)  pp. 225–236</TD></TR>
<TR><TD valign="top">[a6]</TD> <TD valign="top">  K. Culik II,   J. Karhumäki,   "Systems of equations over a free monoid and Ehrenfeucht's Conjecture"  ''Discrete Math.'' , '''43'''  (1983)  pp. 139–153</TD></TR>
<TR><TD valign="top">[a7]</TD> <TD valign="top">  A. Ehrenfeucht,   G. Rozenberg,   "Elementary homomorphisms and a solution to D$0$L-sequence equivalence problem"  ''Theoret. Comput. Sci.'' , '''7'''  (1978)  pp. 169–183</TD></TR>
<TR><TD valign="top">[a8]</TD> <TD valign="top">  J. Engelfriet,   G. Rozenberg,   "Fixed point languages, equality languages, and representation of recursively enumerable languages"  ''J. Assoc. Comput. Mach.'' , '''27'''  (1980)  pp. 499–518</TD></TR>
<TR><TD valign="top">[a9]</TD> <TD valign="top">  V.S. Guba,   "The equivalence of infinite systems of equations in free groups and semigroups with finite subsystems"  ''Mat. Zametki'' , '''40'''  (1986)  pp. 321–324  (In Russian)</TD></TR>
<TR><TD valign="top">[a10]</TD> <TD valign="top">  J. Karhumäki,   "On the equivalence problem for binary D0L systems"  ''Inform. Control'' , '''50'''  (1981)  pp. 276–284</TD></TR>
<TR><TD valign="top">[a11]</TD> <TD valign="top">  J. Karhumäki,   "The impact of the D$0$L-problem"  G. Rozenberg (ed.)  A. Salomaa (ed.) , ''Current Trends in Theoretical Computer Science. Essays and Tutorials'' , World Sci.  (1993)  pp. 586–594</TD></TR>
<TR><TD valign="top">[a12]</TD> <TD valign="top">  P. Prusinkiewicz,   M. Hammel,   J. Hanan,   R. Měch,   "Visual models of plant development"  G. Rozenberg (ed.)  A. Salomaa (ed.) , ''Handbook of Formal Languages'' , '''III''' , Springer  (1997)  pp. 535–597</TD></TR>
<TR><TD valign="top">[a13]</TD> <TD valign="top">  G. Rozenberg,   A. Salomaa,   "The mathematical theory of $L$-systems" , Acad. Press  (1980)</TD></TR>
<TR><TD valign="top">[a14]</TD> <TD valign="top">  A. Salomaa,   "Equality sets for homomorphisms of free monoids"  ''Acta Cybernetica'' , '''4'''  (1978)  pp. 127–139</TD></TR>
<TR><TD valign="top">[a15]</TD> <TD valign="top">  A. Salomaa,   M. Soittola,   "Automata-theoretic aspects of formal power series" , Springer  (1978)</TD></TR>
<TR><TD valign="top">[a16]</TD> <TD valign="top">  A. Thue,   "Über unendliche Zeichereichen"  ''Kra. Vidensk. Selsk. Skr. I. Mat.-Nat. Kl.'' , '''7'''  (1906)</TD></TR>
</table>

{{TEX|part}}