Controlled Iteration Grammars and Hyper-AFL's

We study $K$-iteration grammars equiped with a control on the application sequence of the substitutions, called $(\Gamma,K)$-iteration grammars. In fact, the control is a language over the indices of the substitutions, prescribing the specific order in which one has to apply the different substitutions ($\Gamma$ is a family of control languages). We show the follwing results: (1) If the family $K$ contains all finite languages, then regular control does not increase the generating power of $K$-iteration grammars. (2) If the families $\Gamma$ and $K$ satisfy some rather simple conditions, then for each $(\Gamma,K)$-iteration grammar, we are able to construct an equivalent propagating $(\Gamma,K)$-iteration grammar. (3) The restrictions on the families $\Gamma$ and $K$ such that the family $(\Gamma,K){\rm ITER}$ of $\Gamma$-controlled $K$-iteration languages becomes a hyper-AFL. (4) The conditions on the families $\Gamma$ and $K$ such that the following holds: $(\Gamma,K){\rm ITER}^{(m)}=(\Gamma,K){\rm ITER}$ for each $m\geq2$. As a simple consequence we obtain: all Lindenmayer-AFL's $(K){\rm ITER}^{(2)}$, $(K){\rm ITER}^{(3)}$, ... , $(K){\rm ITER}^{(m)}$, ... , $(K){\rm ITER}$ are hyper-AFL and moreover they are all identically the same: $(K){\rm ITER}^{(m)}=(K){\rm ITER}$ for each $m\geq2$.