MATHEMATICS ON THE MEMBERSHIP QUESTION IN SOME LINDENMAYER-SYSTEMS BY

Lindenmayer-systems are a family of string-generating systems, and several types can be distinguished, of different strength. The subject of this article is the membership question in the languages generated by determinate, no-input Lindenmayer-systems (or, shortly, DOL-languages). For propagating DOL-systems (whioh contain no production rules yielding the empty string) the question is easily snswered. For DOL-systems in general it can be solved in two steps, involving the construction of an intermediate “backbone ” system, which is propagating. NOTATION; DESURIPTION OF DOL-SYSTEMS The notation conforms to common usage in language theory, and I shall only state a few conventions. Any sequence of elements of an alphabet Z is called a word over Z; A is the empty word. If a~ & then ua=ua, etc.; &=A. Z * is the Kleenean closure of Z. # Z denotes the number of elements of Z. 1~1 denotes the length of a word w. If 6 is a mapping of a set into itself, then 82(z) =6(6(z)), etc.; 60(z) =x. Elements (or letters) of an alphabet shall usually be denoted by (r, t,..., words by u, v, w, x,.... Esystems were first proposed by A. LINDENMAYER in 1968 [3], as a model for the development of filamentous organisms. DOL-systems, which form a subclass of the L-systems, can be formally described as follows: DEFINITION. A DOL-system is an ordered triple B = (Z, 6, WO), where Z (the alphabet) is a finite, nonempty set, 8 (the set of ~o&u.&kms) is a total mapping over.Z. from Z into C*, and wo (the tionz) is a non-empty word The domain of 8 is extended from.Z to Z * in a natural way, by definin