Has anyone ever considered the class of languages $X$ generated by 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 am not 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 that such 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.

  • 2
    $\begingroup$ Almost sounds like W-grammars, but not quite. $\endgroup$ – Brian Tompsett - 汤莱恩 Jan 4 '16 at 23:38
  • 2
    $\begingroup$ Can you be more precise about what you mean by "growing context-sensitive productions which are described by context-free rules"? I'm not sure what you mean by a context-sensitive production that can be described by a context-free rule. Can you give a mathematical definition and/or an example or two? $\endgroup$ – D.W. Jan 4 '16 at 23:56
  • $\begingroup$ Your description is vague enough and there is enough similarities with W-grammars that I'd not be surprised if there is a mapping between the two (your example seems easily mappable for instance). $\endgroup$ – AProgrammer Jan 11 '16 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.