On the degree of synchronization of k1TOL and k1ETOL systems (Q1124362)

K-limited TOL and ETOL systems (abbreviated klTOL, respectively klETOL) were introduced by \textit{D. Wätjen} [J. Inf. process. Cybern. 24, No.6, 267-285 (1988; Zbl 0661.68069)]. The main differenc from the usual Lindenmeyer systems is that instead of th fully parallel rewriting of L- systems exactly min\(\{\) k,{\#}\({}_{\alpha}(w)\}\) occurrences of any symbol a in the word w considered, have to be rewritten. The degree of synchronization of a kl(E)TOL system G (Syn(G)) is the number of its tables (finite substitutions) and for a kl(E)TOL language L, \(Syn_ k(L)=\min \{Syn(G)| G\) is a kl(E)TOL system with \(L(G)=L\}\). It is proved that there exists an infinite hierarchy: \({\mathcal L}_ m(KlTOL)\varsubsetneq {\mathcal L}_{m+1}(klTOL)\) and \({\mathcal L}_ m(lTOL)\varsubsetneq {\mathcal L}_{m+1}(lTOL)\), for all k, \(m\in N\) where \({\mathcal L}_ m(klTOL)\) denotes the family of languages generated by klTOL systems with degree of synchronization m and \({\mathcal L}_ m(lTOL)=\cup^{\infty}_{k=1}{\mathcal L}_ k(klTOL)\). Because for every klETOL language L we have \(Syn_ k(L)\leq 2\), for every k, the corresponding hierarchy for klETOL systems reduces to \({\mathcal L}_ 1(klETOL)\varsubsetneq {\mathcal L}_ 2(klETOL)\).