Stability in L systems (Q802316)

The paper studies stability in L systems using a new approach. Given an L system G, a word w is said to be k-stable in G if, once w occurs in a derivation, the derivation can proceed no more than k steps before the next occurrence of w. The set of k-stable words in an L system is called by the author the k-stable language of the system. Thus, the notion of k- stable languages is a generalization of the notion of adult languages introduced by \textit{A. Walker} [Lect. Notes Comput. Sci. 15, 201-215 (1974; Zbl 0296.68077)]. The class of k-stable languages of OL systems is shown to be equal to the class of adult languages of OL systems. It is also proved that similar results hold for the class of k-stable languages of PIL and IL systems, respectively. Hence, a new characterization of context-free, context-sensitive and recursively enumerable languages in terms of parallel grammars is obtained.