Cross-serial dependencies

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.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 3 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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. 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 \geq 1\} . Since L can be mapped to L' by the following map: x, y, z \mapsto \epsilon; 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' is not context-free.

L' =\{ a^m b^n c^m d^n | m, n \geq 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^pb^pc^pd^p in the language, and mark the letters b^pc^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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1337042403 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

4 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.