{'fraction_non_alphanumeric': 0.03811722578213343, 'fraction_numerical': 0.007491519035054655, 'mean_word_length': 4.603220696937698, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Word Order in German: A Formal Dependency Grammar Using a Topological Hierarchy

This paper proposes a description of German word order including phenomena considered as complex, such as scrambling, (partial) VP fronting and verbal pied piping. Our description relates a syntactic dependency structure directly to a topological hierarchy without resorting to movement or similar mechanisms.


Introduction
The aim of this article is to describe the word order of German verbs and their complements. German word order is not free, but based on fairly simple rules, forming what is usually called topological model, which subdivides the sentence into a hierarchy of topological domains that are themselves composed of fields (Vorfeld, Mittelfeld, right bracket…) (Drach, 1937;Bech, 1955). We start from a syntactic dependency tree, i.e. an unordered tree whose nodes are labeled with the words of the sentence, and whose branches are labeled with syntactic relations among the words (subject, direct object…).
The syntactic dependency structure only encodes subcategorization and modification and must be completed by the communicative structure (partition into theme/rheme, focus…), which plays a fundamental role in word order. It permits us to choose among all the different possible orders corresponding to a given dependency structure. In this paper we do not pursue this problem any further, but have limited our description to the link between dependency and topology. Note that it is fundamental to our approach that syntactic structure does not include word order.
To get the words in order, we group them in a hierarchy of phrases. The nature and the position of these phrases are constrained by our topological model. For instance, a non-finite verb can open two kinds of topological phrases, either a phrase, which we call domain, with positions for all of its dependents, or a restricted phrase, which forms the verb cluster, with no positions for dependents other than predicative elements. These two kinds of phrases must be placed in very different topological positions. The fact that we pass through a (topological) phrase structure in order to relate dependency and word order distinguishes our approach from usual dependency grammars (Mel'cuk & Pertsov, 1987;Bröker, 1998;Kahane et al., 1998;Duchier & Debusmann, 2001). The description of German word order closest to our analysis is the HPSG grammar of Kathol (1995; see also Reape 1994), who proposes linearization rules exclusively based on a formalization of the topological structure. However, as required by the formalism he uses, a regular phrase structure, which we do not need in our analysis, still underlies the structures obtained.
Our work constitutes a syntactic module which links (unordered) syntactic structures with topological phrase structures. Syntactic structures are related to semantic structures, whereas topological phrase structures are related to phonological structures. In other words, our work lies within the scope of the general framework of Meaning-Text-Theory (Mel'cuk 1988), which considers the modeling of a language as a modular (bi-directional) correspondence between meaning and text. It must be clear that, in contrast to X-bar syntax, our topological phrase structure does not represent the syntactic structure of the sentence. Although the dependency information is essential in its construction, the phrase structure only represents topology, i.e. the surface grouping of the words. Topological phrases can be directly related to prosodic groups, and topology represents an intermediate level between dependency and phonology. In Section 2, the results of our findings are presented, without recourse to any mathematical formalism, in the usual terminology of traditional German grammars. In Section 3, a mathematical formalism is proposed to state the rules and the grammar fragment described in Section 2.

Description
Word order in German is much freer than in English. The dependency tree of Fig. 1, which will be our reference example, has a few dozen linearizations: ( In this paper, we do not attempt to characterize well-formed German dependency trees although we recognize that such a characterization is essential if we attempt to describe the acceptable sentences of German.

Topological model
The internal structure of a domain is a sequence of fields. For example, the main domain is the underlying pattern of a declarative sentence, and it consists of the following sequence of five fields: [Vorfeld, left bracket, Mittelfeld, right bracket, Nachfeld]. A domain resembles a box whose ordered compartments, called fields, can themselves accommodate new boxes. In addition to the rules listing the fields of each type of box, we propose two further types of rules: • rules that indicate into which field a word can go-depending on the position of its governor; • rules that indicate which type of box a word can create when it is placed into a given field. The hierarchy of boxes forms the phrase structure we construct.

Word order rules
We have established the following rules for the linear order of verbs and their dependents: • The finite verb takes the second position of the main domain, the left bracket. This verb is also called V2. • A non-finite verb depending on V2 can go into the right bracket. 2 As a result, it opens a reduced phrase with only one position for a verbal dependent (see Section 2.8 for another possibility). If a subsequent third verb joins the verb already in the right bracket, it will again open a phrase with a position to its left, and so on. The verbal constituent occupying the right bracket is called the verb cluster. • Some non-verbal dependents, such as separable verbal prefixes (for example the an of anfangen 'begin'), predicative adjectives, and nouns governed by a copular verb or a support verb, can go into the right bracket (the prefix even forms one word with its following governor). In contrast to verbs, these elements do not usually open up a new position for their dependents, which consequently have to be placed somewhere else. 3 • One dependent (verbal or non-verbal) of any of the verbs of the main domain (V2, any verb in the right bracket or even an embedded verb) has to occupy the first position, called the Vorfeld (VF, prefield). • All the other non-verbal dependents of the verbs in the domain (V2 or part of the verbal cluster) can go in the Mittelfeld (MF, middle-field). • Some phrases, in particular sentential complements (complementizer and relative clauses), prepositional phrases, and even some sufficiently heavy noun phrases, can be positioned in a field right of the right bracket, the Nachfeld (NF, after-field). Like the Mittelfeld, the Nachfeld can accommodate several dependents. • When a verb is placed in any of the Major Fields (Vor-, Mittel-, Nachfeld), it opens a new embedded domain.
In the following section we illustrate our rules with the dependency tree of Fig. 1 and show how we describe phenomena such as scrambling and (partial) VP fronting.

Non-embedded construction and "scrambling"
Let us start with cases without embedding, i.e. where the subordinated verbs versprochen 'promised' and zu lesen 'to read' will go into the right bracket of the main domain (Fig. 2). The constituents which occupy the left and right brackets are represented by shadowed ovals. The other three phrases, niemand 'nobody', diesem Mann 'to this man', and das Buch 'the book', are on the same domain level; one of them has to take the Vorfeld, the other two will go into the Mittelfeld. We obtain thus 6 possible orders, among them (1a) and (1b). There are nevertheless some general restrictions on the relative constituent order in the Mittelfeld. We do not consider these rules here (see for instance Lennerz 1977, Uszkoreit 1987), but we want to insist on the fact that the order of the constituents depends very little on their hierarchical position in the syntactic structure. 4 Even if the order is not free, there (i) Er fängt gleich zu schreien an.
He begins right_away to shout AN. 'He begins to shout right away.' 4 Dutch has the same basic topological structure, but has lost morphological case except on pronouns. For a simplified description of the order in the Dutch Mittelfeld, we have to attach to each complement placed in the Mittelfeld its height in the syntactic are restrictions that weigh more heavily than the hierarchical position: pronominalization, focus, new information, weight, etc. The fact that a verbal projection (i.e. the verb and all of its direct and indirect dependents) does not in general form a continuous phrase, unlike in English and French, is called scrambling (Ross, 1967). This terminology is based on an erroneous conception of syntax that supposes that word order is always an immediate reflection of the syntactic hierarchy (i.e. every projection of a given element forms a phrase) and that any deviation from this constitutes a problem. In fact, it makes little sense to form a phrase for each verb and its dependents. On the contrary, all verbs placed in the same domain put their dependents in a common pot. In other words, there is no scrambling in German, or more precisely, there is no advantage in assuming an operation that derives 'scrambled' sentences from 'nonscrambled' ones. As we have said, when a verb is placed in one of the major fields, it opens an embedded domain. We represent domains by ovals with a bold outline. In the situation of Fig. 3, where zu lesen 'to read' opens an embedded domain, hat 'has' and versprochen 'promised' occupy the left and right bracket of the main domain and we find three phrases on the same level: niemand 'nobody', diesem Mann 'to this man', and das Buch zu lesen 'to read the book'. The embedded domain can go into the Vorfeld (1c), the Nachfeld (1d), or the Mittelfeld (1a,e). Note that we obtain the word order (1a) a second time, giving us two phrase structures:

Embedding
(2) a.  (2a) and (2b) correspond to different prosodies (the left border of the right bracket is clearly marked with an accent on the first syllable of the radical). Finally, the existence of this ambiguity is also confirmed by the contrast between full infinitives (with zu) and bare infinitives (without zu): Bare infinitives cannot form an embedded domain outside of the Vorfeld. Consequently, there are two different prosodies for (3a) (with or without detachment of das Buch 'the book' from zu lesen 'to read'), whereas only one prosody without detachment is permitted for (3b), although (3a) and (3b) have isomorphic dependency trees. Evidence comes also from the written form recommending a comma for (3a) (i.e. preference for the embedded structure), whereas the comma is not allowed for (3b).

b. Niemand will das Buch lesen
'Nobody wants to read the book.'

Emancipation
The dependents of a verb do not have to be in their governor's domain: They can be 'emancipated' and end up in a superior domain. For example, in Fig. 4, the verb zu lesen 'to read' has created an embedded domain from which its dependent das Buch 'the book' has been emancipated. We have thus four complements to place in the superior domain, allowing more than thirty word orders, among them (1f)

Word order in the right bracket
German permits different orders inside the verb cluster. The tense auxiliaries haben 'have' (past) and werden 'become/will' (future) also allow their dependents to take a place on their right in the right bracket (Oberfeldumstellung or auxiliary flip; Bech, 1955) (4a). The dependents of this verb go again on the left side of their governor, just as in standard order (we thus obtain V 1 V 2 , V 1 V 3 V 2 , V 1 V 4 V 3 V 2 ) but it can also join the place to the left of the auxiliary (we thus obtain the marginal Zwischenstellung V 3 V 1 V 2 (4c), V 4 V 3 V 1 V 2 ). The governed verbs V 2 accepting this inverse order form a closed class including the modal and perception verbs and some others (helfen, 'help', the causative/permissive lassen 'make/let' … -haben 'have' itself also allows this right-placement, which suffices to explain the cases of 'double flip' as in (4b) giving V 1 V 2 V 4 V 3 ). Note that the dependent of haben 'have' is the bare infinitive. This form, called the Ersatzinfinitiv, is also possible or even preferable for certain verbs when the auxiliary is in V2 position.
He will the book have read can. 'He will have been able to read the book.' b. Ich glaube, dass er das Buch wird haben lesen können.
I believe that he the book read will can. 'I believe that he will be able to read the book.' In related languages like Dutch or Swiss-German, which have the same topological structure, the standard order in the right bracket is somewhat similar to the German Oberfeldumstellung. The resulting order gives rise to cross serial dependencies (Evers 1975, Bresnan et al. 1982) Such constructions have often been studied for their supposed complexity. With our subsequent description of the Oberfeldumstellung, we obtain a formal structure that applies equally to Dutch. Indeed, the two structures have identical descriptions with the exception of the relative order of dependent verbal elements in the right bracket (keeping in mind that we do not describe the order of the Mittelfeld).

Relatives and pied-piping
Relative clauses open an embedded domain with the main verb going into the right bracket. The relative pronoun takes the first position of the domain, but it can take other elements along (pied-piping) (5). German differs from English and Romance languages in that even verbs can be brought along by the relative pronoun (5b). Before we discuss the topological structure of relative clauses, we will discuss their syntactic representation. Following Tesnière (1959) and numerous analyses that have since corroborated his analysis, we assume that the relative pronoun plays a double syntactic role: • On one hand, it has a pronominal role in the relative clause where it fills a syntactic position. • On the other hand, it plays the role of a complementizer allowing a sentence to modify a noun. For this reason, we attribute to the relative pronoun a double position: as a complementizer, it is the head of the relative clause and it therefore depends directly on the antecedent noun and it governs the main verb of the relative clause. As a pronoun, it takes its usual position in the relative clause. It is now possible to give the word order rules for relative clauses. The complementizing part of the relative pronoun opens an embedded domain consisting of the complementizer field (Kathol 1995), Mittelfeld, right bracket, and Nachfeld. The main verb that depends on it joins the right bracket. The other rules are identical to those for other domains, with the group containing the pronominal part of the relative pronoun having to join the other part of the pronoun in the complementizer field. In a sense, the complementizer field acts like the fusion of the Vorfeld and the left bracket of the main domain: The complementizing part of the pronoun, being the root of the dependency tree of the relative clause, takes the left bracket (just like the top node of the whole sentence in the main domain), while the pronominal part of the relative pronoun takes the Vorfeld. The fact that the pronoun is one word requires the fusion of the two parts and hence of the two fields into one. Note that verbal pied-piping is very easy to explain in this analysis: It is just an embedding of a verb in the complementizer field. Just like the Vorfeld, the complementizer field can be occupied by a non-verbal phrase or by a verb creating an embedded domain.

Formalization
A grammar in the formalism we introduce in the following will be called a Topological Dependency Grammar.

Definition of the Grammar
For a grammar, the parameters to instantiate are the vocabulary V, the set of (lexical) categories C, the set of syntactic relations R, the set of box names B, the set of field names F, the initial field i, the order of permeability of the boxes, which is a partial ordering on B (used for emancipation) and four sets of rules: 5

Box description rules:
The rule b f1 f2 … fn indicates that the box b consists of the list of fields f1, f2, …, fn.

Field description rules:
The pair (f,ε) in F×{!,?,+, * } indicates that the field f has to contain exactly one element (!), at most one element (?), at least one element (+) or any number of elements ( * ).

Correspondence rules (between the dependency and the topological structure):
The rule (r,c1,c2,f2,b) indicates that a word w2 of category c2, that exhibits a dependency of type r on a word w1 of category c1, can go into field f2 of a box containing w1, if this box is separated from w1 by borders of type ≤ b (in other words, the parameter b controls the emancipation).

Box creation rules:
The rule (c,f,b,f') indicates that a word of category c, placed into a field f, can create a box b and go into the field f' of this box. Box creation rules are applied recursively until a lexical rule of type (c,f,b,-) is encountered where b is a lexical box with a unique lexical field, into which the word has to be placed.

Phrase structure derivation starting from a dependency tree
The word labeling the root node of the tree is placed into the initial field i. Box creation rules are then activated until the word is placed in a lexical field (-). A correspondence rule is activated for one of the dependents of the root node, placing it in an accessible field. Just as for the root node, box creation rules are activated until the word is assigned to a lexical field. This procedure continues until the whole tree is used up. Each time a box creation rule is triggered, a box is created and a description rule for this box has to be activated. Finally, the constraints of the field description rules have to be respected (e.g. a field requiring at least one element can not remain empty).

Example of a grammar
We will now instantiate our formalism for the German grammar fragment described in section 2 (leaving aside non-verbal elements in the right bracket) and we will put forward the derivation of (1f) with this grammar (Fig.5).

Correspondence rules
Positioning of the first verb in the right bracket: 6 (r, Y, V, ], -) Positioning of a verb to the left of the preceding verb in the right bracket: (r, V, V¬fin, o, vc) Positioning of a verb to the right of the preceding verb in the right bracket: 7 (r, AV¬inf, EV, u, -) 6 The last parameter (-) indicates that the right bracket of a given domain is not accessible when emancipating an element from an embedded domain. 7 Auxiliaries with zu do not allow auxiliary flip: (i) * Er meint das Buch zu haben lesen können.
He thinks the book to have read can.
Positioning of a non-verbal element in a major field: 8 (r, V, X, f, ed)

Box creation rules
Creation of the main domain in the initial field: (Vfin, i, md, [) Creation of an embedded domain in a major field: (V¬fin, f, ed, ]) Creation of a verbal cluster in the right bracket or the Unterfeld: (V,]/u,vc, h) Creation of a verbal box in the Oberfeld: (V, o, vb, h) Positioning of a verb: (V, [/h, v, -) Creation of a non-verbal phrase: (X, f, xp, ?) Creation of a domain for a relative clause: 9 ("C", f, cd, "cf")

Conclusion
We have shown how to obtain all acceptable linear orders for German sentences starting from a syntactic dependency tree. To do that we have introduced a new formalism which constructs phrase structures. These structures differ from X-bar phrase structures in at least two respects: First, we do not use the phrase structure to represent the syntactic structure of the sentence, but only for linearization, i.e. as an intermediate step between the syntactic and the phonological levels. Secondly, the nature of the phrase opened by a lexical element depends not only on the syntactic position of this element, but also on its position in the topological structure (e.g. the different behaviors of a verb in the right bracket vs. in a major field).
We have to investigate further in various directions: From a linguistic point of view, the natural continuation of our study is to find out how the communicative structure (which completes the dependency tree) restricts us to certain word orders and prosodies and how to incorporate this into our linearization rules. It would also be interesting to attempt to describe other languages in this formalism, configurational languages such as English or French, as well as languages such as Russian where the surface order is mainly determined by the communicative structure. However, German is an especially interesting case because surface order depends strongly on both the syntactic position (e.g. finite verb in V2 or Vfinal position) and the communicative structure (e.g. content of the Vorfeld). From a computational point of view, we are interested in the complexity of our formalism. It is possible to obtain a polynomial parser provided that we limit the number of nodes simultaneously involved in non-projective configurations (see Kahane et al. 1998 for similar techniques). Such limitations seem reasonable for Germanic languages (e.g. verb