free languages then ${\mathord{\it P}}={\mathord{\it NP}}$.

In fact it can be shown directly that R-AVGs also produce non-context free languages.

The context sensitive language $\{a^nb^nc^n\}$ is generated by an R-AVG.

(Sketch) Typically, the R-AVG that generates the language $\{a^nb^nc^n\}$ first generates an amount of $a$’s then an amount of $b$’s and finally an amount of $c$’s. Let us assume that the grammar generates $i$ $a$’s. During the derivation, the feature graph can be used to store the amount of $a$’s that is produced. Once the grammar starts to produce $b$’s , the feature graph will force the grammar to generate exactly $i$ $b$’s and next to generate exactly $i$ $c$’s as well.

The Honest Parsability Constraint and Consequences {#HPC}
==================================================

According to Theorem \[PNP\], it is unlikely that the languages generated by R-AVGs can be limited to those languages with a polynomial time recognition algorithm. Trautwein [@lp-95-01] showed that all R-AVGs have nondeterministic polynomial time algorithms. Is it perhaps the case that any language that has a nondeterministic polynomial time recognition algorithm can be generated by an R-AVG. Does there exist a tight relation between time bounded machines and R-AVGs as e.g., between LBAs and CSLs? The answer is that 