On the power of L-systems in image generation (Q1342508)

The authors show that D0L-systems are surprisingly powerful as generators of black-and-white-images. It is shown that, for either the vector or turtle geometry interpretation, D0L-systems can generate all images that can be defined by regular sets (or equivalently by iterative matrix homomorphisms of Shallit and Stolfi). Further, an extension of turtle geometry interpretation is introduced that enables \(L\)- systems to generate gray-tone images. It is shown that using this extension D0L- systems can simulate weighted finite automata (WFA). Since the authors recently developed an efficient inference algorithm for WFA that allows the approximate efficiently any gray-tone image by a WFA, the same holds also for approximation by D0L-systems.