next up previous contents
Next: Tree Adjoining Grammars Up: Beyond concatenation Previous: Johnson's `combines'

Sequence union

[71], and [72] discuss a relation called sequence union to analyze discontinuous constituents. The sequence union of the sequences s1, s2 and s3 is true, iff each of the elements in s1 and s2 occur in s3, and moreover, the original order of the elements in s1 and s2 is preserved in s3. For example, the sequence union of the sequences $ \langle$a, b$ \rangle$ and $ \langle$c, d$ \rangle$ and s3 is true, iff s3 is any of the sequences:

\eq
\lefteqn{\langle a,b,c,d\rangle}~~~~\\
\lefteqn{\langle a,c,b,d\rangle}~~~~...
...efteqn{\langle c,a,d,b\rangle}~~~~\\
\lefteqn{\langle c,a,b,d\rangle}~~~~
\eeq

Reape presents an HPSG-style grammar [69] for German and Dutch which uses the sequence union relation on word-order domains. The grammar handles several word-order phenomena in German and Dutch. Word-order domains are sequences of signs. The phonology of a sign is the concatenation of the phonology of the elements of its word-order domain. In `rules', the word-order domain of the mother sign is defined in terms of the word-order domains of its daughter signs. For example, in the ordinary case the word-order domain of the mother simply consists of its daughter signs. Thus, for example, in the rule s $ \rightarrow$ np vp the word-order domain associated with s would consist of the sequence which consists of the signs associated with np and vp. However, in specific cases it is also possible that the word-order domain of the mother consists of the elements of the word-order domains of the daughters. Thus, in case of a rule x $ \rightarrow$ yz in which the word-order domain associated with y is the sequence $ \langle$y1, y2$ \rangle$, and the word-order domain associated with z is $ \langle$z1$ \rangle$, then the word-order domain associated with x is any of the sequences $ \langle$y1, y2, z$ \rangle$, $ \langle$y1, z, y2$ \rangle$, $ \langle$z, y1, y2$ \rangle$.

The following German example by Reape clarifies the approach, where I use indices to indicate to which verb an object belongs.

\begin{exam}
\begin{flushleft}
\dots es$_i$\ ihm$_j$\ jemand$_k$\ zu lesen$_i$\ ...
...had\\
\dots {\it someone had promised him to read it}
\end{flushleft}\end{exam}
It is assumed that a `flat' verb phrase rule selects the arguments of a verb (in one go), and that furthermore in case of a vp argument, the word-order domain of this vp is sequence-unioned with the word-order domain of the verb; the non-vp arguments of the verb become simply members of the word-order domain of the mother of this verb-phrase rule. Figure 4.4 shows a parse tree of this sentence, where the nodes of the derivation tree are labelled by the string associated with that node. The indices relate verbs with their arguments. This tree can be read in a bottom-up fashion, as follows. Firstly, the verb `zu lesen' selects an np, resulting in a verb-phrase with word-order domain $ \langle$npi, vi$ \rangle$. This verb-phrase is one of the arguments of the verb `versprochen'. As this argument is a verb-phrase its word-order domain is sequence-unioned. A (possible) result is the word-order domain $ \langle$npi, npj, vi, vj$ \rangle$. The verb `hat' also selects an np and a vp. The elements of the vp are sequence unioned, the np is simply added to the word-order domain, which results in a possible word-order domain $ \langle$npi, npj, npk, vi, vj, vk$ \rangle$. Note that strings are defined with respect to word-order domains. Sequence union is defined on such domains. The strings of the derivation tree are thus only indirectly related through the corresponding word-order domains.

Figure 4.4: Simplified parse tree of Reape's analysis of German verb-clusters, using sequence union.
\begin{figure}
\begin{center}
\leavevmode
\unitlength1pt
\beginpicture
\setplot...
...on
\put{\hbox{$es_i$}} [Bl] at 283.77 18.00
\endpicture
\end{center}\end{figure}

Linear precedence statements are defined with respect to word-order domains. These statements can be thought of either as well-formedness conditions on totally ordered sequences, or alternatively as constraints limiting possible orders of a word-order domain. Note that order information is monotonic; the sequence union relation cannot `change' the order of two ordered items.


next up previous contents
Next: Tree Adjoining Grammars Up: Beyond concatenation Previous: Johnson's `combines'
Noord G.J.M. van
1998-09-30