in an attribute-value language ${\cal A}(A,V,L)$. An [*annotated constituent structure tree*]{} is a triple $\mathopen{<}T,F,h\mathclose{>}$, where $h$ is a function that maps internal nodes in $T$ onto variables in $F$.

A [*lexicon*]{} is a finite subset of ${\mathord{\rm Lex}}\times
{\mathord{\rm Cat}}\times  {\cal A}(A,\{x_0\},L)$. A set of [*syntactic rules*]{} is a finite subset of $\bigcup_{i\geq 1} {\mathord{\rm Cat}}\times{\mathord{\rm Cat}}^i\times{\cal A}(A,\{x_0,\ldots,x_i\},L)$. An [*attribute-value grammar*]{} is a triple $\mathopen{<}\mathord{\rm lexicon},\mathord{\rm rules},\mathord{\rm start}
\mathclose{>}$, where lexicon is a lexicon, rules is a set of syntactic rules and start is an element of ${\mathord{\rm Cat}}$.

\

1.  [**[@balcazar.ea:88 p .150]** ]{} A class ${\cal C}$ of sets is [*recursively presentable*]{} iff there is an effective enumeration $M_1, M_2, \ldots$ of deterministic Turing machines which halt on all their inputs, and such that ${\cal C} = \{
    L(M_i) \mid i = 1, 2, \ldots \}$.

2.  We say that a class of grammars ${\cal G}$ is [*recursively presentable*]{} iff the class of sets $\{L(G) \mid G \in {\cal G} \}$ is recursively presentable.

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

The only formulas that are allowed in the attribute-value language of restricted attribute-value grammars (R-AVGs) are path-equations and conjunctions of path-equations (i.e. disjunctions and negations are out). We will 