that is recognized by $M$. Add the set of rules that guarantee that only strings that can be produced with a polynomial number of rules can be produced by the grammar.

Veer out the HPC
================

Instead of creating a counter of logarithmic size as we do in Appendix \[hpavg\], it is quite straightforward to construct a counter of linear size (or exponential size if there is enough time). In fact, for well-behaved functions, the construction of a counter gives a method to enforce any desired time bound constraint on the recognition problem for attribute-value grammars. For instance, for nondeterministic exponential time we could define the Linear Dishonest Parsability Constraint (LDP) (allowing a linear exponential number of steps) which would give.

The class of languages generated by R-AVGs obeying the LDP condition is exactly ${\mathord{\it NE}}$.

Acknowledgements {#acknowledgements .unnumbered}
================

We are indebted to E. Aarts and W.C. Rounds for their valuable suggestions on an early presentation of this work.

[BDG88]{} J. Balcázar, J. Díaz, and J. Gabarró. . Springer-Verlag, New York, 1988.

P. Blackburn and E. Spaan. A modal perspective on the computational complexity of attribute value grammar. , 2(2):129–169, 1993.

N. Chomsky. Three models for the description of 