An Efficient Derivation Method for DT0L Systems and a Measure of Derivation Complexity

An efficient derivation method for DTOL systems is proposed. The method, called a lazy derivation, makes two morphisms from a morphism applied at every step. One morphism simulates the original derivation but it is an identity over a set of letters on which every morphism of the system is a bijective coding. The other morphism recovers the original derivation. Generative complexities of a word by normal and Jazy derivations are defined. It is shown that, for any integer k ≥ 1, there is a DTOL system such that the generative complexities per letter of a word w by normal and lazy derivations are Θ(|w|1/k) and Θ(1), respectively.