problem with the HPC is of course that it is not a syntactic property of grammars. The question whether a given AVG satisfies the HPC (or the OLP for that matter) may well be undecidable. Nonetheless, we can produce a set of rules that, when added to an attribute-value grammar [*enforces*]{} the HPC. The newly produced language is then a subset of the old produced language with an ${\mathord{\it NP}}$ recognition algorithm. Because of the fact that our addition may simulate any polynomial restriction, we regain the full class of AVG’s that satisfy the HPC. In fact

The class, P-AVGL, of languages produced by the HP-AVGs is recursively presentable.

We will give a detailed construction of such a set of rules in Appendix \[hpavg\]. The existence of such a set of rules and the work of Johnson now gives the following theorem.

\[npishpavg\] For any language $L$ that has an ${\mathord{\it NP}}$ recognition algorithm, there exists a restricted attribute-value grammar $G$ that respects the HPC and such that $L=L(G)$.

(Sketch) Let $M$ be the Turing machine that decides $w\in L$. Use a variation of Johnson’s construction of a Turing machine to create an R-AVG that can produce any string $w$ 