The proposed head-driven algorithm for TAG terminates for all lexicalized TAGs. Note though that the algorithm terminates for a strictly larger set of TAGs. Consider the class of TAGs in which each initial tree is lexical, and where furthermore each auxiliary tree is branching. That is, we do not require that auxiliary trees have an anchor, as long as they have (at least) one substitution node. This for example allows an auxiliary tree like the following in figure 4.24. A Tag is semi-lexicalized in case its initial trees are all lexicalized, and its auxiliary trees are either lexicalized or branching.
We might call grammars that allow such auxiliary trees `semi-lexicalized'.Such auxiliary trees may in fact be very useful. To treat modification with auxiliary trees in a lexicalized TAG we need to assume, for example, that each preposition is ambiguous, given that prepositional phrases may modify different categories (at least noun phrases, verb phrases and adjectival phrases), and may occur as arguments. In semi-lexicalized TAGs on the other hand we can simply assume that a preposition corresponds to an initial tree. Furthermore for each possible modification there is one auxiliary tree.
It is not difficult to see that the head-driven parser in fact terminates for semi-lexicalized grammars. This is so, because adjunctions are seen as chain-rules and hence applied in a bottom-up fashion. For that reason no left-recursion can arise: the trees that are derived always grow (in terms of the length of their yield).
![\begin{figure}
\par\begin{center}
\leavevmode
\unitlength1pt
\beginpicture
\set...
...r ''3223379 $\ pp}} [Bl] at 38.26 18.00
\endpicture
\end{center}\par\end{figure}](img369.png)