an R-AVG (R-AVGL) includes the class of context free languages (CFL). It follows that any easily parsable class of languages (like CFL) is a proper subset of R-AVGL, unless ${\mathord{\it P}}={\mathord{\it NP}}$. Likewise, R-AVGL is a proper subset of the class of context sensitive languages, unless ${\mathord{\it NP}}={\mathord{\it PSPACE}}$. In Section \[HPC\] we propose a further refinement on the off-line parsability constraint, which allows R-AVGs that respect this constraint to capture [*precisely*]{} complexity classes like ${\mathord{\it NP}}$ or ${\mathord{\it NEXP}}$. That is, for any language $L$ that has an ${\mathord{\it NP}}$-parser, there exists an R-AVG, say $G$, such that $L=L(G)$. Though our refinement, the [*honest parsability constraint*]{} is probably not a property that can be decided for arbitrary R-AVGs, we show that R-AVGs can be equipped with restricting mechanisms that enforce this property. The techniques that prove Theorem \[ravgl\] and Theorem \[npishpavg\] result from Johnson’s work. Therefore, the proofs of these theorems are deferred to the appendices.

Definitions and Notation
========================

Attribute-Value Grammars
------------------------

The definitions in this section are in the spirit of [@johnson:88 Section 3.2] and [@smolka:92 Sections 3–4]. Consider three sets of pairwise disjoint symbols.

$A$, the finite set of constants, denoted ($a,b,c,\dots$)

$V$, the countable set 