Growth of strings in context dependent Lindenmayer systems

Growth functions of context dependent Lindenmayer systems are investigated. Bounds on the fastest and slowest growth in such systems are derived, and a method to obtain (P)DIL growth functions from (P)D2L growth functions is given. Closure of context dependent growth functions under several operations is studied with special emphasis on an application of the firing squad synchronization problem. It is shown that, although all growth functions of DILs using a one letter alphabet are DOL growth functions, there are growth functions of PDILs using a two letter alphabet which are not. Several open problems concerning the decidability of growth equivalence, growth type classification etc. of context dependent growth are shown to be undecidable. As a byproduct we obtain that the language equivalence of PDILs is undecidable and that a problem proposed by Varshavsky has a negative solution.

• View at Publisher

See Also
techReport Growth of strings in context dependent Lindenmayer systems : (prepublication) P.M.B. Vitányi (Paul)