the off-line parsability constraint that forces the R-AVG to have no chain- or $\epsilon$-rules is just too restrictive to allow such a connection. The following trick to alleviate this problem has been observed earlier in complexity theory. The off-line parsability constraint(OLP) [@johnson:88] relates the amount of “work” done by the grammar to produce a string linearly to the number of terminal symbols produced. It is therefore a sort of honesty constraint that is also demanded of functions that are used in e.g., cryptography. There the deal is, for each polynomial amount of work done to compute the function at least one bit of output must be produced. In such a way, for polynomial time computable functions one can guarantee that the inverse of the function is computable in nondeterministic polynomial time.

As a more liberal constraint on R-AVGs we propose an analogous variation on the OLP

A grammar $G$ satisfies the Honest Parsability Constraint(HPC) iff there exists a polynomial $p$ s.t. for each $w$ in $L(G)$ there exists a derivation with at most $p({\mathopen|w\mathclose|})$ steps.

From Smolka’s algorithm and Trautwein’s observation it trivially follows that any attribute-value grammar that satisfies the HPC (HP-AVG) has an ${\mathord{\it NP}}$ recognition algorithm. The 