String concatenation

In order to check what string a given derived tree dominates, we could define the relation `yield' which - procedurally speaking - travels a tree in a top-down fashion and collects the terminal symbols at the leaves of the tree. However, note that TAG derivations exhibit a monotonicity property with respect to the order of words. Once a certain order has been established, this order cannot be changed anymore. For this reason, all trees which are derived during a derivation yield a string which is a subsequence of the string to be parsed. For that reason an important reduction of the search space can be obtained by checking whether an hypothesized derived tree indeed yields a subsequence of the string to be parsed. Furthermore, such a check then also implies that it is not necessary anymore, to check whether the topmost derived tree yields the desired string: this is necessarily the case, because a topmost derived tree has used all words in the input and furthermore yields a subsequence.

The following predicates are obtained. Note that we now assume an extra argument position through which we percolate the input string. The predicate $\mbox{\it head\_corner}$ will be modified later.

The predicate $\mbox{\it yield\_subseq}$ straightforwardly checks whether the first argument, a tree, yields a subsequence of the second argument, a string.