Complexity of L-Systems

Despite of the fact that the complexity theory forms a significant and rapidly growing part of theoretical computer science the study of complexity of L-systems is in its beginnings. In the following three études we wish to sketch out some possible directions of such investigations. From the two standard ways of dealing with complexity in TCS — computational and descriptional complexity — we prefer to discuss here the descriptional complexity of L-systems. A survey of descriptional complexity and its comparison with computational complexity of languages can be found in [2]. Results on the computational complexity of L-systems and that on subword complexity of L-systems will be omitted here.