of the (natural) language, and on the other hand is restrictive enough to preserve feasibility. For a discussion on the linguistic significance of such restrictions, see [@perrault:84].

Johnson [@johnson:88] proved that attribute-value grammars that are as restrictive as being equipped with a rewrite grammar that is regular can already give rise to an undecidable recognition problem. Obviously, to be of any practical use, the rewrite grammar or the attribute-value language must be more restrictive. Johnson proposed to add the [*off-line parsability constraint*]{}, which is respected if the rewrite grammar has no chain- or $\epsilon$-rules. Then, the number of applications in a production is linear and the size of the structure corresponding to the partial productions is polynomial. Hence as by a modification of Smolka’s algorithm [@smolka:92] consistency of intermediate steps can be checked in quadratic time, the complexity of the recognition problem can at most be (nondeterministic) polynomial time. This observation was made in [@lp-95-01], which also has an ${\mathord{\it NP}}$-hardness proof of the recognition problem.

We further investigate the properties of these restricted AVGs (R-AVGs). In the next section, we give some more formal definitions and notations. In Section \[WGC\] we show that the class of languages generated by 