Has anyone ever considered the class of languages $X$ generatedby growing context-sensitive productions which are described by context-free rules?In particular, I wonder if there is a NP-complete language inside this class.The proof that any language in GCSF is also in $P$ uses the fact that there is a constant $d>1$ such that for all productions $a ::= b$ we have $|b| > d \cdot |a|$, so it does not work for $X$ directly. It seems that $X$ lies somewhere between GCSF and general CSF, but I amnot so sure even in the second inclusion.For example, for generating the language $\{a^nb^nc^n \mid n\ge 0\}$ one may write the grammar$$\begin{array}{rcl} S &\to& \varepsilon \mid aBc\\ aB(b^*)c &\to& aaB(b^*)bcc\\ B &\to& b\end{array}$$ where $(b^*)$ have to match the same expression in both parts of the second production.Note that every instance of this production is growing, so it's plausible thatsuch grammars are nicer than general CSGs or general W-grammars, and so I thought that they might have already be studied by someone.  Of course, this is only a toy example. In the actual problem I'm dealing with, the left part of productions (which goes for $(b^*)$ in the example above) should satisfy quite a complicated balance condition with a few types of brackets.
Growing context-sensitive grammars with context-free rules
formal languages;np complete;formal grammars