“a man” and “walks” should both end in a node labeled “singular.” Such a constraint is called a “path equation” in the attribute-value language.

A rewrite grammar [@chomsky:56] can be enriched with an AVL to construct an Attribute Value Grammar(AVG), which consists of pairs of rewrite-rules and logical formulas. The rewrite rule is applicable to a production (nonterminal) only if the logical formula that expresses the relation between left- and right-hand side of the rule evaluates to true. The recognition problem for attribute-value grammars can be stated as: Given a grammar $G$ and a string $w$ does there exist a derivation in $G$, that respects the constraints given by its AVL, and that ends in $w$. As the intermediate productions correspond to feature graphs this question can also be formulated as a question about the existence of a consistent sequence of feature graphs that results in a feature graph describing $w$. For the rewrite grammar, any formalism in the Chomsky hierarchy (from regular to type $0$) can be chosen. From a computational point of view it is of course most desirable to restrict oneself to a formalism that on the one hand gives enough expressibility to describe a large fragment 