Cross-serial dependencies

A diagram showing cross-serial dependency using lines and colors to represent the dependent pairs.

A schematic showing cross-serial dependencies. Notice that the w's and v's, which represent words, each form respective series. Notice also that the lines representing the dependency relations mutually overlap.

In linguistics, cross-serial dependencies (also called crossing dependencies by some authors) occur when the lines representing the dependency relations between two series of words cross over each other. They are of particular interest to linguists who wish to determine the syntactic structure of natural language; languages containing an arbitrary number of them are non-context-free. By this fact, Dutch and Swiss-German have been proven to be non-context-free.

Examples

File:Cross-serial dependencies.png

A Swiss-German sentence containing cross-serial dependencies (shown as lines between the verbs and their objects). The English translation with its dependencies, which do not cross, is shown for comparison.

Swiss-German

As Swiss-German allows verbs and their arguments to be ordered cross-serially, we have the following example, taken from Shieber:

...mer	em Hans	es	huus	hälfed	aastriiche.
...we	Hans (dat)	the	house (acc)	help	paint.

That is, "we help Hans paint the house."

Notice that the sequential noun phrases em Hans (Hans) and es huus (the house), and the sequential verbs hälfed (help) and aastriiche (paint) both form two separate series of constituents. Notice also that the dative verb hälfed and the accusative verb aastriiche take the dative em Hans and accusative es huus as their arguments, respectively.

Dutch

Shows a dependency tree of the Swiss-German sentence: words are projected to a node with edges between words in syntactic relationship (e.g. subject or object relation between noun and respective verb). One can see a non-projective edge, that is one that crosses the projection line of a word. The arc from swim (zwemmen) to children (kinderen) crosses the projection line of the verb saw.

Dependency structure for a Dutch sentence containing a cross-serial dependency: dat Jan de kinderen zag zwemmen (that Jan saw the children swim). The tree structure surfaces how a projection line of a word (zag: saw) is crossed by a syntactic dependency relation between words it governs. This makes the tree non-projective.

Bresnan et al. provide the following Dutch examples for cross-serial dependencies with two, three and four levels.

...dat	Jan	de	kinderen	zag	zwemmen
...that	Jan	the	children	see-past	swim-inf

That is, "...that Jan saw the children swim."

Dependency tree similar to the previous one for the sentence with one nesting level less. This time there are even more edges crossing each other.

Dependency tree with cross-serial dependencies for the Dutch sentence dat Jan Piet de kinderen zag helpen zwemmen (that Jan saw Piet help the children swim).

...dat	Jan	Piet	de	kinderen	zag	helpen	zwemmen
...that	Jan	Piet	the	children	see-past	help-inf	swim-inf

That is, "...that Jan saw Piet help the children swim."

...dat	Jan	Piet	Marie	de	kinderen	zag	helpen	laten	zwemmen
...that	Jan	Piet	Marie	the	children	see-past	help-inf	make-inf	swim-inf

That is, "...that Jan saw Piet help Marie make the children swim."

Non-context-freeness

Let $L_{SG}$ to be the set of all Swiss-German sentences. We will prove mathematically that $L_{SG}$ is not context-free.

In Swiss-German sentences, the number of verbs of a grammatical case (dative or accusative) must match the number of objects of that case. Additionally, a sentence containing an arbitrary number of such objects is admissible (in principle). Hence, we can define the following formal language, a subset of $L_{SG}$:$$L=\text{De Jan}\text{ s}\ddot{\mathrm{a}}\text{it}\text{ das}\text{ mer}\text{ (d'chind)}{}^m\text{ (em}\text{ Hans)}{}^n\text{ s}\text{ huus}\text{ h}\ddot{\mathrm{a}}\text{nd}\text{ wele}\text{ (laa)}{}^m\text{ (h}\ddot{\mathrm{a}}\text{lfe)}{}^n\text{ aastriiche.}$$Thus, we have $L=L_{SG}\cap L_r$, where $L_r$ is the regular language defined by $$L=\text{De Jan}\text{ s}\ddot{\mathrm{a}}\text{it}\text{ das}\text{ mer}\text{ (d'chind)}{}^{+}\text{ (em}\text{ Hans)}{}^{+}\text{ s}\text{ huus}\text{ h}\ddot{\mathrm{a}}\text{nd}\text{ wele}\text{ (laa)}{}^{+}\text{ (h}\ddot{\mathrm{a}}\text{lfe)}{}^{+}\text{ aastriiche.}$$where the superscript plus symbol means "one or more copies". Since the set of context-free languages is closed under intersection with regular languages, we need only prove that $L$ is not context-free (, pp 130–135).

After a word substitution, $L$ is of the form $\{x{a}^m{b}^{n}y{c}^m{d}^{n}z|m,n\ge 1\}$. Since $L$ can be mapped to $L^{\prime }$ by the following map: $x,y,z\mapsto ϵ;a\mapsto a;b\mapsto b;c\mapsto c$, and since the context-free languages are closed under mappings from terminal symbols to terminal strings (that is, a homomorphism) (, pp 130–135), we need only prove that $L^{\prime }$ is not context-free.

$L^{\prime }=\{a^m{b}^n{c}^m{d}^n|m,n\ge 1\}$

is a standard example of non-context-free language (, p. 128). This can be shown by Ogden's lemma.

Suppose the language is generated by a context-free grammar, then let

$p$

be the length required in Ogden's lemma, then consider the word

$a^p{b}^p{c}^p{d}^p$

in the language, and mark the letters

$b^p{c}^p$

. Then the three conditions implied by Ogden's lemma cannot all be satisfied.

All known spoken languages which contain cross-serial dependencies can be similarly proved to be not context-free. This led to the abandonment of Generalized Phrase Structure Grammar once cross-serial dependencies were identified in natural languages in the 1980s.

Treatment

Research in mildly context-sensitive language has attempted to identify a narrower and more computationally tractable subclass of context-sensitive languages that can capture context sensitivity as found in natural languages. For example, cross-serial dependencies can be expressed in linear context-free rewriting systems (LCFRS); one can write a LCFRS grammar for {aⁿbⁿcⁿdⁿ | n ≥ 1} for example.