a. the memory fades<\/em>
b. a new computer arrives<\/em>\u2026
c. the person she really likes waits<\/em>\u2026<\/p>\n\n\n\n
However, this is not true for all of the individual components of the phrases, as can be seen in (1.3). Therefore, one assumes the existence of an abstract category called a constituent<\/em> to which one or more words can belong and for which rules like \u201enoun phrases can be followed by verbs\u201c can be postulated (Jurafsky and Martin, 2009, chapter 12).<\/p>\n\n\n\n (1.3) Note: The asterisk marks constructions that are not grammatical.<\/p>\n\n\n\n Traditional views of constituency demand that constituents consist of adjacent words. This is rooted in a system for modelling languages called context-free grammar<\/em> (CFG) (Chomsky, 1956), a generative device that derives sentences by using rewrite rules, starting with an initial symbol. The derivation path marks a hierarchy of constituents that can be arranged into a derivation\/parse tree<\/em>. Figure 1.1 gives an example for such a description. Note that the tree only contains non-crossing edges which is why it is called projective<\/em> or continuous<\/em>.<\/p>\n\n\n\n This view of constituency was adopted by many treebanks<\/em>. Treebanks are linguistic corpora in which the sentences have been annotated with syntactic representations (e.g. constituency trees) (Jurafsky and Martin, 2009, chapter 12). However, this leads to difficulties when analysing syntactic phenomena that are believed to exhibit non-local dependencies. While the analysis of German or other languages with varying degrees of free word order evidently questions the projective approach, the English language also exhibits a fair amount of discontinuous phenomena, see (1.4) and (1.5).<\/p>\n\n\n\n (1.4) b. den Dank<\/em> m\u00f6chte ich nicht annehmen<\/em> c. ohne Scham <\/em>scheinen sie das komplette Buffet aufgegessen<\/em> zu haben (1.5) Some treebanks like the English Penn Treebank<\/em> (Marcus et al., 1993) opted to mark discontinuous phenomena through indexing and trace nodes, i.e. empty nodes in the place where a discontinuous subsection of the sentence would be expected in \u201estandard\u201c word order. This is motivated by the tradition of analysing discontinuities as instances of transformation or syntactic movement as introduced by Chomsky (1975). The tree in figure 1.2 features three cases of co-indexing. While such a strategy acknowledges the existence of discontinuous relationships, the long-range dependencies of the markers cannot be fully captured by traditional parsing techniques for projective grammars and often remain unused.<\/p>\n\n\n\n In a number of treebanks like the German NeGra (Skut et al., 1998) and TIGER treebanks (Brants et al., 2004) or English discontinuous Penn Treebank<\/em> (Evang and Kallmeyer, 2011) (DPTB) long-range dependencies are represented by crossing edges and constituents with non-adjacent elements. The resulting trees are called discontinuous constituent trees<\/em>. Figure 1.3 shows an example from the NeGra corpus.<\/p>\n\n\n\n In order to capture syntactic descriptions with discontinuous constituents, several formalisms have been proposed. Among these linear context-free rewriting systems<\/em> (LCFRS) (Vijay-Shanker et al., 1987) have been shown to be a natural candidate for accurately covering the notion of discontinuous constituents employed by the aforementioned treebanks.<\/p>\n\n\n\n Being a foundation for many natural language processing tasks, parsing speed is a key concern and a driver of active research. Parsing LCFRS is non-trivial in terms of efficiency. The adaptation of traditional chart parsing for LCFRS results in a polynomial time complexity of O(n^(3*dim(G))) where n is the length of a sentence and dim(G) is the maximal number of discontinuous blocks of a constituent in the grammar. Transition-based parsing approaches aim at reducing this factor by doing away with the need for an explicit grammar. Instead, an artificial neural network is trained to produce discontinuous constituent trees given only raw text input using supervised learning<\/em> on large annotated corpora. Errors in prediction are backpropagated through the network resulting in optimisations of its parameters. In this way, it implicitly learns to identify regularities that it can effectively use to predict trees for unseen data. A recent and elegant proposal for a neural stack-free transition-based parser developed by Coavoux and Cohen (2019) successfully allows for the derivation of any discontinuous constituent tree over a sentence in worst-case quadratic time.<\/p>\n\n\n\n
a. *the fades<\/em>
b. *<\/em>new arrives<\/em>\u2026
c. *likes spends<\/em>\u2026<\/p>\n\n\n\n![\"\"](\"https:\/\/mielczarek.de\/wp-content\/uploads\/2023\/11\/image-800x322.png\")
<\/figure>\n\n\n\n
a. sie packte<\/em> ihre Werkzeuge ein<\/em>
she packed her tools up
\u2019she packed her tools\u2018<\/p>\n\n\n\n
the thanks want he not accept
\u201ahe does not want to accept the thanks\u2018<\/p>\n\n\n\n
without shame seem they the complete buffet eaten to have
\u201athey seem to have eaten the entire buffet without shame\u2018<\/p>\n\n\n\n
a. areas of the factory<\/em> were particularly dusty where the crocidolite was used<\/em> (Evang, 2011)
b. a man<\/em> entered who was wearing a black suit<\/em> (McCawley, 1982)<\/p>\n\n\n\n![\"\"](\"https:\/\/mielczarek.de\/wp-content\/uploads\/2023\/11\/image-1-800x320.png\")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/mielczarek.de\/wp-content\/uploads\/2023\/11\/image-2-800x307.png\")
<\/figure>\n\n\n\n