Word order domains in categorial grammar

Koen Versmissen Onderzoeksinstituut voor Taal en Spraak (OTS) Universiteit Utrecht Trans 10 NL – 3512 JK Utrecht The Netherlands Koen.Versmissen@let.ruu.nl

1 Introduction

Research within the logically oriented branch of Categorial Grammar (CG) has given a lot of attention over the past few years to possible treatments of discontinuity phenomena. This was a reaction to the obvious inadequacy of the Lambek calculus as a vehicle for describing realistic natural language grammar fragments in view of its inherent context-freeness, cf. Pentus (1992). The present paper can be seen as part of that development, since it explores yet another such possibility. My proposal is based on the theory of word order domains (or just domains for short), developed by Mike Reape (1992, 1994, to appear) within the framework of Head-Driven Phrase Structure Grammar (HPSG). Furthermore, it makes use of modalities in CG, in the spirit of Moortgat (1995), Kurtonina and Moortgat (1995). What I intend to show here is that these modalities provide a natural means of importing domains into CG.

The structure of the paper is as follows. In Section 2, I introduce Reape’s main ideas, and provide a couple of illustrative examples. In Section 3, I turn to a discussion of the definition and use of modalities within categorial logics. Having laid the groundwork I then show in Section 4 how to translate the structural part of Reape’s analysis in categorial terms by means of these modalities. In Section 5, I will discuss the possibilities afforded by modalities to account for domain structure in more detail. This discussion is a precursor to Section 6, in which the architecture of grammars of the kind introduced in Section 4 is made more principled, thus facilitating the addition of other dimensions to it. One such addition is discussed in Section 7, where I show how such a grammar can be extended to a multimodal categorial grammar in which the interaction postulates for its unary and binary residuals provide for a type logical explanation of the linear precedence part of Reape’s proposal. Finally, in Section 8, I will reflect a little on the implications of the material presented here, and indicate some possible directions of future research.

2 Word order domains

In his introduction to Reape (to appear), the author notes that “Nearly all modern grammatical theories derive word order from the terminal yield of phrase structure trees”. As an alternative he presents his theory of word order domains, which “rejects surface syntax and its role in determining word order.” Reape lists the following as the five main claims of his approach in its simplest, most general form:

1. Phrasal word order is determined within locally definable word order domains, which are ordered sequences of constituents.

2. Phrasal word order domains are composed compositionally from their daughter word order domains.

3. Lexical entries do not have word order domains.

4. The functor of a phrasal constituent is an element of its mother’s domain.

5. Either

(a) a nonfunctor daughter is an element of its mother’s domain, or

(b) the elements of a nonfunctor daughter’s domain are elements of its mother’s domain, and furthermore they may appear discontinuously or nonadjacently in the mother’s domain — provided the relative order of the elements of the daughter domain are preserved in the mother’s domain.

When the last option is chosen, the daughter domain is said to have been domain unioned^{1} into its mother’s domain. The order of elements within a domain is determined by linear precedence (LP) constraints.

Let’s follow Reape in illustrating his theory of word order domains by means of the following German “cross-serial” subordinate clause:

(1) daß that

es_{3} it[acc]

ihm_{2} him[dat] jemand_{1} someone[nom] zu lesen_{3} to read versprochen_{2} promised

hat_{1} has

‘that someone promised him to read it’

In order to analyse this clause, four extra assumptions are needed beyond the ones mentioned above. These are:

1. The configuration [S NP[nom] VP] is ungrammatical in German. Instead, verbs take all their complements as sisters in clauses.

2. The following LP constraint holds: NP ≺ V.

3. A verb follows any verb that it governs. Government is here basically what Bech (1955) calls status government.

4. All of the verbs in the sentence under consideration domain union their VP complements.

The verb zu lesen subcategorises for a direct object, so we can form the VP es zu lesen with domain (2).

(2) [VP [NP es][V zu lesen]]

The NP es precedes the verb as required by the LP statement NP ≺ V. The past participle versprochen subcategorises for an indirect object and a zu-infinitival VP. Unioning the domain of the es zu lesen, which is such a VP, into the VP domain of which versprochen is the head, we can form the VP es ihm zu lesen versprochen with domain (3).

1Domain union is similar to the shuffle operator of formal language theory.

(3) [VP [NP es][NP ihm][V zu lesen][V versprochen]]

Actually, since our assumptions say nothing about the relative order of the two NPs, they also allow us to derive the VP ihm es zu lesen versprochen, with domain (4).

(4) [VP [NP ihm][NP es][V zu lesen][V versprochen]]

Finally, since hat subcategorises for a past participial VP and a nominative NP, we can form the clause es ihm jemand zu lesen versprochen hat with domain (5).

(5) [VP [NP es][NP ihm][NP jemand][V zu lesen][V versprochen][V hat]]

Again, since the relative order of NPs is unconstrained, there are further possibilities, giving rise to the following five domains, which all describe clauses that are grammatical as well:

[VP [NP es][NP jemand][NP ihm][V zu lesen][V versprochen][V hat]] [VP [NP ihm][NP es][NP jemand][V zu lesen][V versprochen][V hat]] [VP [NP ihm][NP jemand][NP es][V zu lesen][V versprochen][V hat]] [VP [NP jemand][NP es][NP ihm][V zu lesen][V versprochen][V hat]] [VP [NP jemand][NP ihm][NP es][V zu lesen][V versprochen][V hat]] (6)

A slightly more involved example is the following sentence:

(7) daß that der Mann the man versucht tried hat, has, zu behaupten, to claim, das Buch the book gelesen read

zu haben to have

‘that the man has tried to claim to have read the book’

In transformational terms, this sentence contains two extraposed VPs. Its presumed deep structure is given in (8) below:

(8) daß der Mann [[das Buch gelesen zu haben] zu behaupten] versucht hat.

From this deep structure (7) can be derived by means of two applications of extraposition.

Within Reape’s theory, this sentence can easily be accounted for. First, a feature x is assumed which indicates whether or not a constituent occurs in extraposed position. For this feature we of course need to add the LP constraint [x −] ≺ [x +]. Furthermore, it is stipulated that extraposed clauses cannot be unioned. With these assumptions, we get the derivation for (7) shown in Figure 1 on the next page.

Word order domains as I described them above contain information about both the structure of an expression and the linear order of its building blocks. In what follows, these two quite distinct kinds of information will be separated from each other. I will first show, in Sections 3 to 6, how the structural information embodied in word order domains can be captured by a CG enriched with unary modalities. In a sense, this already suffices as a categorial account of Reape’s theory, since the set of LP constraints can be used to determine the admissible orderings of the elements in sequent antecedents.^{2} It turns out, however, that it is fairly easy to account for linear order as well in the type logic. This is the subject of Section 7.

2I omit the straightforward induction argument showing that both ways of going about this yield equivalent results.

[S[NP derMann][V versucht][V hat] [VP [V zubehaupten][VP [NP dasBuch][V gelesen][V zuhaben]]]]

[NP derMann] [VP [V versucht]

[VP [V zubehaupten]

[VP [NP dasBuch][V gelesen][V zuhaben]]]]

[VP [V zubehaupten] [VP [NP dasBuch][V gelesen][V zuhaben]]]

[V zubehaupten] [VP [NP dasBuch][V gelesen][V zuhaben]]

[V zuhaben] [VP [NP dasBuch][V gelesen]]

[NP dasBuch]  [V gelesen]

[V versucht]

[V hat]

(daß) der Mann versucht hat, zu behaupten, das Buch gelesen zu haben

Figure 1: Domain tree

3 Modalities in categorial grammar

Unary operators, or modalities, have been around in CG since the beginning of this decade. Different modalities were introduced for several purposes. In Morrill (1990) modalities described intensional formulas in the semantics. In Morrill et al. (1990) they were used to allow limited application of otherwise forbidden structural rules, following the lead of Girard (1987). Because of their origin and the way they were used, the proof rules for these early modalities were modeled after those of well-known modal logics such as K, S4 and S5.

More recently in a number of papers (Moortgat and Oehrle (1993), Moortgat (1995), Kurtonina and Moortgat (1995)) a new family of modal operators was proposed. The fundamental behaviour of these modalities is governed solely by residuation.

For a binary operator • with residuals / and \, residuation has the following familiar appearance:

A ⊢ C/B iff A • B ⊢ C iff B ⊢ A\C

The appropriate semantics for these very basic operators is the most general one: Kripke frames (cf. Došen (1992), Kurtonina (1995)). Binary operators are interpreted in such frames by means of ternary relations R^{3} on the underlying domain as follows:

[[A • B]] = {c | ∃ab(R^{3}cab & a ∈ [[A]] & b ∈ [[B]]}
[[C/B]] = {a | ∀bc((R^{3}cab & b ∈ B)→c ∈ C)}
[[A\C]] = {b | ∀ac((R^{3}cab & a ∈ A)→c ∈ C)}

This semantics is illustrated in the picture below:

[figure: \begin{matrix}C/B \\ A \\ a \end{matrix}; R^{3}cab; \begin{matrix}A\C \\ B \\ b \end{matrix}; \begin{matrix}c \\ A • B \\ C \end{matrix}]

In the case of a unary operator ◇ and its residual □, residuation has the following shape:

◇A ⊢ B iff A ⊢ □B

The semantics is now defined on the basis of a binary relation R^{2} as shown below:

[[◇A]] = {b | ∃a(R^{2}ba & a ∈ [[A]]}
[[□B]] = {a | ∀b(R^{2}ba → b ∈ [[B]]}

These definitions can be elucidated in a picture similar to the previous one:

[figure: A a □B; R^{2}ba; ◇A b B]

In a sequent calculus, it is necessary to introduce a unary sequent bracketing operator (.)^{◇}. The rules for ◇ and □ are then the following ones:

{Γ ⊢ A \atop (Γ)^{◇} ⊢ ◇A} ^{[◇R]}  {Γ[(A)^{◇}] ⊢ B \atop Γ[◇A] ⊢ B} ^{[◇L]}

{(Γ)^{◇} ⊢ A \atop Γ ⊢ □A} ^{[□R]}  {Γ[A] ⊢ B \atop Γ[(□A)^{◇}] ⊢ B} ^{[□L]}

As a simple illustration of how these rules interact, I show below the derivation of four fundamental sequents:

{A ⊢ A \atop (A)^{◇} ⊢ ◇A} ^{[◇R]} ◇A ⊢ ◇A [◇L] {A ⊢ A \atop (□A)^{◇} ⊢ A} ^{[□L]} □A ⊢ □A [□R]

{A ⊢ A \atop (□A)^{◇} ⊢ A} ^{[□L]} ◇□A ⊢ A [◇L] {A ⊢ A \atop (A)^{◇} ⊢ ◇A} ^{[◇R]} A ⊢ □◇A [□R]

To get a feel for the behaviour of these modalities it is perhaps most useful to think of them as a kind of degenerated form of the binary residuals.^{3} Under this analogy ◇A is to be thought of as the product of some “modalising” type M with A, whereas □A is comparable to M\A.

For binary residuals it holds that A • (A\B) ⊢ B. After all, A\B is ‘a B looking for an A’, and taking the product with A provides this missing type. On the other hand not all material of type B can necessarily be split up in this way, so the implication only goes in the given direction.

Similarly, B ⊢ A\(A • B) is a valid sequent. The reason is that A\(A • B) denotes material that combines with something of type A to the juxtaposition of materials of types A and B, respectively. Obviously, material of type B belongs to this class. Again, the implication goes only one way: not everything which combines with material of type A into A • B is necessarily of type B.

Reverting to the analogy introduced earlier we can look at material of type □B as looking for ‘structure’ — either a ◇ or the corresponding structural bracketing of the sequent antecedent. Therefore we find that ◇□B ⊢ B, but not the other way round: not all material of type B needs to have arisen from a fulfilled need for structuring. And finally of course B ⊢ □◇B, since type B material is a particular instance of material that becomes of type ◇B when provided with the appropriate structure — but again not the other way round, since there may be other things that become a B under such beneficial conditions. In terms of derivable sequents, the analogy looks like this:

3In Versmissen (1995) I show that this intuition can be given formal content, leading to a new family of embedding theorems and conjoinability results for categorial calculi.

M • (M\B) ⊢ B ⊢ M\(M • B)
◇□B ⊢ B ⊢ □◇B

Just like several product operators can coexist, it is possible to have a number of modal operators in one calculus. Indeed, my translation of Reape’s work into categorial terms in the next section makes essential use of a multitude of unary operators. In order for different modalities to be discernible from each other they need to be labelled. I will write ⟨L⟩ and ⌈L⌉ for ◇ and □ labelled with L, respectively. The superscript identifying the corresponding structural brackets will now be the label rather than just a diamond. Together with the non-directed mode of combination I will be using this leads to the following calculus, where the comma is associative and commutative:^{4}

A ⊢ A

Γ ⊢ A Δ, B ⊢ C Δ, Γ, A→B ⊢ C ^{[→L]}  {Γ, A ⊢ B \atop Γ ⊢ A→B} ^{[→R]}

{Γ[(A)^{k}] ⊢ B \atop Γ[⟨k⟩A] ⊢ B} ^{[⟨k⟩L]}  {Γ ⊢ A \atop (Γ)^{k} ⊢ ⟨k⟩A} ^{[⟨k⟩R]}

{Γ[A] ⊢ B \atop Γ[(⌈k⌉A)^{k}] ⊢ B} ^{[⌈k⌉L]}  {(Γ)^{k} ⊢ A \atop Γ ⊢ ⌈k⌉A} ^{[⌈k⌉R]}

4 Domains in categorial grammar

As I showed in the last section, the use of Moortgat-style modalities naturally introduces a notion of unary bracketing into CG. In case there is more than just one modality, each of these operators is linked to a (labelled) unary bracketing operator on sequent antecedents. In this section, I will show how this fact enables us to mimic Reape’s domain rules within CG in a straightforward way.

I will limit myself here to a categorial account of the structural part of Reape’s ideas. It is therefore sufficient to use a non-directed calculus. The logical treatment of linear precedence constraints is deferred to Section 7.

The basic idea is to translate the subcategorisation requirements into categorial type assignments, where the modal status of an argument determines whether or not it domain unions into its mother’s domain. A category such as NP→S combines into an S with any material that constitutes an NP. Since this combination does not involve any modal operators, and the underlying calculus is both associative and commutative, the material forming the NP→S and that forming the NP end up together in the same domain. This is the categorial counterpart of domain unioning, and it is the default in a associative and commutative logic.

4A Cut-rule and left and right rules for the product could be added to this calculus without any problem, but I leave these out since I won’t need them.

If an argument needs to be prevented from domain unioning into its mother’s domain, the material constituting that argument must be enclosed in brackets. This can be taken care of in two ways, namely by either the argument or the functor. The most common situation in linguistics is the first one, where certain categories intrinsically project a domain. For instance, the fact that major categories such as noun phrases and sentences are typically domains can be captured by prefixing all positive occurrences of types NP and S with the corresponding □. With such a type assignment, a sentence like der Mann läuft receives the bracketing

((derMann)NP läuft)S

as can be seen from the derivation below:

N ⊢ N

NP ⊢ NP

(⌈NP⌉NP)NP ⊢ NP

(N→⌈NP⌉NP, N)NP ⊢ NP

(der, Mann)NP ⊢ NP

{S ⊢ S \atop (⌈S⌉S)S ⊢ S}

((der, Mann)NP, NP→⌈S⌉S)S ⊢ S

((der, Mann)NP, läuft)S ⊢ S

Neither pair of brackets can be left out. If the NP-brackets were omitted, we would end up with the unprovable sequent ⌈NP⌉NP ⊢ NP rather than with (⌈NP⌉NP)NP ⊢ NP, which latter sequent can be inferred from the axiom NP ⊢ NP by the ⌈NP⌉ left rule. Similar remarks obtain for the S-brackets.

Occasionally, a functor determines that one or more of its arguments are domains. This is reflected in a categorial type assignment by prefixing the type of those arguments with the appropriate diamond. For example, an extraposed VP-argument can be specified by prefixing the type VP with ⟨x⟩. With this type assignment, a verb phrase such as versuchen, es zu lesen receives the bracketing

versuchen((es)NPzulesen)x

which is illustrated by the following derivation:

NP ⊢ NP

(⌈NP⌉NP)NP ⊢ NP

(es)NP ⊢ NP VP ⊢ VP

(es)NP, NP→VP ⊢ VP

(es)NP, zulesen ⊢ VP

((es)NP, zulesen)x ⊢ ⟨x⟩VP VP ⊢ VP

⟨x⟩VP→VP, ((es)NP, zulesen)x ⊢ VP

versuchen, ((es)NP, zulesen)x ⊢ VP

5 More on modalities

Now that I’ve shown how modalities can be used to model word order domains, I will take a step back and further explore their logical properties.

In the table below, I show the results of different combinations of ◇A, A and □A on both sides of a sequent T ⊢ U. The table entries indicate the extra structure needed on the left hand side to make this sequent derivable. In other words, an entry of type T means that the sequent is derivable as such, (T)^{◇} means that brackets are needed around the left hand type, and ‘−’ means that no structure added to the left hand side of the sequent can make it derivable.

⊢  □A  A  ◇A

□A  T  (T)^{◇}  ((T)^{◇})^{◇}

A  −  T  (T)^{◇}

◇A  −  −  T

The second column of this table reflects the case where a category may or may not choose to project a domain, whereas the second column reflects the fact that a functor has the option of turning an argument into a domain.

There is a peculiarity in the top right corner of this table: if both the argument and the functor specify the domainhood of the argument, it receives double bracketing. It is questionable whether this is what we really want from a linguistic point of view. While it is true that several domain boundaries may be present at a certain place in a sentence, these are usually not two instances resulting from a single combination of two pieces of linguistic information. If we want to prevent these double boundaries from occurring we can add the following^{5} interaction postulate:

◇A ⇔ ◇◇A (9)

For modalities in general the following equivalences hold:

□◇□A ⇔ □A
◇□◇A ⇔ ◇A

If we add the above interaction postulate, most modalisations of a given type become equivalent to each other, leaving only five that are essentially different. The interaction between these five types is illustrated in the table below:

5I use A ⇔ B as an abbreviation for the conjunction of A ⊢ B and B ⊢ A.

⊢  □A  ◇□A  A  □◇A  ◇A

□A  T  (T)^{◇}  (T)^{◇}  (T)^{◇}  (T)^{◇}

◇□A  −  T  T  T  (T)^{◇}

A  −  −  T  T  (T)^{◇}

□◇A  −  −  −  T  (T)^{◇}

◇A  −  −  −  −  T

The behaviour of the types ◇□A and □◇A in this table (which depends in no way on the presence of the interaction postulate (9)) is quite interesting. With regards to ◇A and □A they behave just like A, but with respect to A itself there are differences. This has the effect that in the argument of a functor the type ◇□A behaves by and large as an A, with the notable difference that it will not combine with a ‘plain’ A. Rather, it requires its argument to have projected a domain. Dually, an expression of type □◇A doesn’t itself project a domain, but requires the functor that wants to combine with it to do so for it. Finally, it will now be clear that if a type A is marked with ◇□ it can ‘overrule’ the requirement of a functor that the argument it takes have projected a domain. Similarly, a functor looking for a □◇A can even domain union an expression that demands that the functor combining with it to project a domain for it.

Digression. Recall the similarity between unary and binary residuation I mentioned in Section 3. It was used to explain the behaviour of unary residuals in terms of binary ones. Exploring this similarity in the other direction, note that a functor looking for a type A • (A\B) (which corresponds to ◇□B) can’t combine with just any material of type B. It requires it to have a left part consisting of type A material. Dually, an expression of type A\(A • B) (which corresponds to □◇B) can be seen as being of type B, but only in the presence of material constituting an A on the left hand side. These insights may be useful in grammar writing, but as far as I know the possibilities of the types I just discussed haven’t been explored yet.

6 Grammar architecture

Grammars designed along the lines sketched in Section 4 are able to account for the basic domain structure facts. Two refinements are needed, however, in order to make them better suited for the addition of such things as the account of word order that will be the topic of the next section.

The first of these refinements is suggested by the discussion in the previous section. I noted there that a functor ⟨L⟩⌈L⌉A→B is similar to the more simple type A→B, except for the fact that it requires its argument to be a L-domain projected from a head ⌈L⌉A. Recall now the observation from Section 4 that major lexical categories such as NP and S project domains, which led us to mark all positive occurrences of such types with the appropriate □. This implies that we can safely prefix all negative occurrences of major types with the appropriate ◇□-combination. This means, for instance, that VPs are then defined as ⟨NP⟩⌈NP⌉NP→⌈S⌉S. There are two reasons for making such a move.

The first one of these was already implicit in the last section: it allows the grammar to state certain exceptions. For example, omitting the □ on a positive occurrence of a major category would in this set up imply that it can’t be the argument to any functor defined in the standard way, while omitting the ◇□ marking on a negative occurrence of a major category would imply that it could combine even with such exceptional arguments.

The second, and in the present context more important reason for adding ◇□ to negative occurrences of major types is the fact that it allows us to “look inside” the domain in question. After all, from a procedural point of view, the ◇□ checks for the presence of a domain by first removing the domain brackets if they are present, and then putting them back, provided that this is licensed by a □ on the head of the phrase. In the middle of this process, the domain lies open, and is therefore ready for inspection. I will use this property in the next section for the implementation of the checking of word order constraints.

The second refinement that is needed has to do with the status of lexical items. Recall that in Reape’s view, lexical entries do not have word order domains. The same is not entirely true of our proposal: all positive occurrences of major categories are prefixed with a □, and therefore project a domain. In particular, this holds for lexical NPs such as es. Lexical entries belonging to non-major categories such as N or to functor categories, on the other hand, do not project a domain.

This latter fact is problematic for an account of linear order. The LP constraints can order domains on the basis of their labels, but how can they recognize, say, an ⟨NP⟩⌈NP⌉NP→⌈S⌉S as being a verb? The solution, in first approximation, is to force the appropriate domain brackets (…)v around it by prefixing its lexical type assignment with ⌈V⌉. This would work fine for the account of linear order, but has as a consequence that all lexical items will constitute one-element domains. This seems unnecessary, and moreover it is undesirable if want to stay as closely as possible to Reape’s proposal, which says that lexical entries do not have word order domains. The solution lies in the observation that the necessary domain brackets can also be added lexically: we can, for instance, assign intransitive verbs the type ⟨v⟩⌈v⌉(⟨NP⟩⌈NP⌉NP→⌈S⌉S). This has a ⟨V⟩ as its outermost connective, allowing a check of the LP constraint, after which the fact that ◇□A ⊢ A allows us to discard the v-modalities.

I could give a formal definition of the translation from basic categorial type assignments to the lexical types implied by the previous discussion, but it seems more insightful to describe it in words:

▷ Lexical entries are prefixed with ⟨L⟩⌈L⌉, where L is the appropriate label for the category, e.g. ⟨v⟩⌈v⌉ for NP→S, ⟨NP⟩⌈NP⌉ for NP, etc.

▷ (Non-lexical) positive occurrences of NP are prefixed with ⌈NP⌉, and similarly for S.

▷ Negative occurrences of NP are prefixed with ⟨NP⟩⌈NP⌉, and similarly for S.

With this in mind, let’s have another look at the two example sentences given in Section 2.

(10) daß that

es_{3} it[acc]

ihm_{2} him[dat] jemand_{1} someone[nom] zu lesen_{3} to read versprochen_{2} promised

hat_{1} has

‘that someone promised him to read it’

(11) daß that der Mann the man versucht tried hat, has, zu behaupten, to claim, das Buch the book gelesen read

zu haben to have

‘that the man has tried to claim to have read the book’

The basic type assignments for the lexical items occurring in these sentences are the following ones, where VP abbreviates NP→S:

es, ihm, jemand : NP
zulesen : NP→VP
versprochen : NP→(VP→VP)
hat, zuhaben : VP→VP
versuchen, zubehaupten : ⟨x⟩VP→VP
der, das : N→NP
Mann, Buch : N

After the translation described above, these lexical entries change to the ones below, where VP now abbreviates ⟨NP⟩⌈NP⌉NP→⌈S⌉S:

es, ihm, jemand : ⟨NP⟩⌈NP⌉NP
zulesen : ⟨v⟩⌈v⌉(⟨NP⟩⌈NP⌉NP→VP)
versprochen : ⟨v⟩⌈v⌉(⟨NP⟩⌈NP⌉NP→(VP→VP))
hat, zuhaben : ⟨v⟩⌈v⌉(VP→VP)
versuchen, zubehaupten : ⟨v⟩⌈v⌉(⟨x⟩VP→VP)
der, das : ⟨det⟩⌈det⌉(N→⌈NP⌉NP)
Mann, Buch : ⟨N⟩⌈N⌉N

Unfortunately, the derivations that prove the grammaticality of the two example sentences are rather unwieldy and therefore impossible to fit onto the page, so that I am forced to leave them to the interested reader. To illustrate what happens, Figure 2 on the next page contains a derivation which proves that der Mann läuft is a grammatical sentence (cf. the derivation in Section 4).

7 Linear precedence constraints

In this section I will show how the categorial grammars discussed in the previous section can be extended in such a way that they also take care of the enforcement of LP constraints. The starting point for this type logical account of LP constraint checking, then, consists of a non-directed CG with unary modalities ⋃_{L∈L}{⟨L⟩, ⌈L⌉}, where < L, ≺> is a partially ordered set of labels. To this calculus we add a directed mode of combination, which will be used to encode linear order. What is needed to make this work is a way of replacing the directed

{N ⊢ N \atop (⌈N⌉N)N ⊢ N}

⟨N⟩⌈N⌉N ⊢ N Mann ⊢ N

NP ⊢ NP
(⌈NP⌉)NP ⊢ NP
⌈NP⌉NP ⊢ ⌈NP⌉NP

N→⌈NP⌉NP, Mann ⊢ ⌈NP⌉NP (⌈det⌉(N→⌈NP⌉NP))det, Mann ⊢ ⌈NP⌉NP ⟨det⟩⌈det⌉(N→⌈NP⌉NP), Mann ⊢ ⌈NP⌉NP der, Mann ⊢ ⌈NP⌉NP

(der, Mann)NP ⊢ ⟨NP⟩⌈NP⌉NP

{S ⊢ S \atop (⌈S⌉)S ⊢ S} ; ⌈S⌉S ⊢ ⌈S⌉S

(der, Mann)NP, ⟨NP⟩⌈NP⌉NP→⌈S⌉S ⊢ ⌈S⌉S

(der, Mann)NP, (⌈v⌉(⟨NP⟩⌈NP⌉NP→⌈S⌉S))v ⊢ ⌈S⌉S

(der, Mann)NP, ⟨v⟩⌈v⌉(⟨NP⟩⌈NP⌉NP→⌈S⌉S) ⊢ ⌈S⌉S

(der, Mann)NP, läuft ⊢ ⌈S⌉S

((der, Mann)NP, läuft)S ⊢ ⟨S⟩⌈S⌉S

Figure 2: Derivation of ((der, Mann)NP, läuft)S

mode by the non-directed mode just in case the linear order of the types involved is consistent with the LP constraints as expressed by the partial order.

The idea is to introduce a third set of auxiliary modalities each of which represents a certain part of a domain by indicating which labels are admissible for the expressions occurring in that part of the domain. This means that we will have modalities ⟨S⟩ and ⌈S⌉ for all S ⊆ L. LP constraint checking is then initiated by ⌈L⌉, the most general of these modalities. As it descends down a structure it ‘divides itself up’ until it arrives at a level where it can be checked against a labelling modality.

This idea leads us to ask ourselves how the relation between sets containing all labels that can occur in some part of a domain can be characterized. In other words, given a domain D = D_{1} D_{2} and denoting by ℓ(D) the set of labels occurring in D we want to find the range of possible pairs < ℓ(D_{1}), ℓ(D_{2}) >.

Suppose we have a domain in which two expressions with label X and an expression with label Y occur. If the LP constraints don’t specify the relationship between X and Y (i.e. they are incomparable in the partial order) it is perfectly alright for the expression labeled Y to be placed in between both expressions labeled X. This means that domains can’t always be split up into pieces the sets of labels occurring in which are disjoint. What we need instead is the following relation between subsets of the partial order L:

S < T iff ∀s ∈ S, t ∈ T : t ⊀ s

It is in fact easy to see that this is the strongest relation for which it is true that it always holds of the sets of labels pertaining to two subparts of a domain, the first of which comes before the other.

With this in mind it is now easy to see how the basic interaction between the directed and the non-directed modes can be achieved. Suppose material for some ordered combination of types is restricted to a subset S of L. In terms of the type language, this means that we’re dealing with ⟨S⟩(A • B). This ordering of A and B is admissible just in case the material constituting these types comes from two subsets T and U of L with T < U. Moreover, all material must be inside S, which means that both T and U must in fact be subsets of S. These observations lead to the following interaction postulate:

⟨S⟩(A • B) ⊢ ⟨T ⟩A ⊗ ⟨U⟩B  if  T, U ⊆ S and T < U

In sequent calculus terms this translates to the following inference rule (the directed mode of combination is indicated by juxtaposition):

{(Γ)^{T} , (Δ)^{U} ⊢ C \atop (Γ Δ)^{S} ⊢ C}  if  T, U ⊆ S and T < U

This single interaction postulate takes care of the main part of the LP constraint checking process. Two things still need to be taken care of:

1. Starting up the LP constraint checking process.

2. Ending the LP constraint checking process.

As I mentioned already, the process is started up by adding the modality ⌈L⌉ in the appropriate places. These places are:

▷ In between the ⟨NP⟩ and the ⌈NP⌉ in front of a NP in negative position (and similarly for S). It’s here that we use the fact that from a procedural point of view the type assignment ⟨NP⟩⌈NP⌉NP causes a NP-domain to be opened and the closed again. In between, we have the opportunity to impose order constraints on the ‘opened’ domain by means of ⌈L⌉.

▷ After domain-specifying diamonds such as ⟨x⟩.

Notice that it is in principle possible to have exceptions to these lexical rules. This means that the LP constraint checking is turned from a global option into a local one: it is possible for a functor to specify that it doesn’t care about the linear order in one or more of its argument domains.

There is once complication here: assigning the type ⟨NP⟩⌈L⌉⌈NP⌉NP to an NP argument of a functor is based on the assumption that the ⌈L⌉ is discarded in the course of the LP constraint checking process. This will be the case in general, but not for lexical entries, since the order checking process bottoms out there. Consequently, the assignment to lexical NPs must be changed from ⟨NP⟩⌈NP⌉NP to ⟨NP⟩⌈L⌉⌈NP⌉NP (and similarly for lexical Ss, should they occur).

The final issue is the termination of the LP constraint checking process. This must happen when a subset modality has descended down to the lexical level. It can then be discarded, provided that the label of the lexical item does in fact lie in the subset specified by the modality. This means that we have the following interaction postulate:

⟨S⟩⟨L⟩A ⊢ ⟨L⟩A  if  L ∈ S

The structural counterpart of this postulate looks as follows:

{Γ[(Δ)^{L}] ⊢ C \atop Γ[((Δ)^{L})^{S}] ⊢ C}  if  L ∈ S

The type assignments to the lexical items in the two example sentences now look as follows (with VP this time being shorthand for ⟨NP⟩⌈L⌉⌈NP⌉NP→⌈S⌉S):

es, ihm, jemand : ⟨NP⟩⌈L⌉⌈NP⌉NP
zulesen : ⟨v⟩⌈v⌉(⟨NP⟩⌈L⌉⌈NP⌉NP→VP)
versprochen : ⟨v⟩⌈v⌉(⟨NP⟩⌈L⌉⌈NP⌉NP→(VP→VP))
hat, zuhaben : ⟨v⟩⌈v⌉(VP→VP)
versuchen, zubehaupten : ⟨v⟩⌈v⌉(⟨x⟩⌈L⌉VP→VP)
der, das : ⟨det⟩⌈det⌉(N→⌈NP⌉NP)
Mann, Buch : ⟨N⟩⌈N⌉N

The relevant LP constraints are det ≺ N and NP ≺ v.

Again, the derivations corresponding to the entire example sentences are of necessity left to the reader. Instead, I give a third derivation of der Mann läuft, split up into two pieces two overcome TEX’s memory limitations:

{N ⊢ N \atop (⌈N⌉N)N ⊢ N}

((⌈N⌉N)N)^{{N}} ⊢ N

(⟨N⟩⌈N⌉N)^{{N}} ⊢ N

(Mann)^{{N}} ⊢ N

NP ⊢ NP

(⌈NP⌉)NP ⊢ NP ⌈NP⌉NP ⊢ ⌈NP⌉NP

N→⌈NP⌉NP, (Mann)^{{N}} ⊢ ⌈NP⌉NP

(⌈det⌉(N→⌈NP⌉NP))det, (Mann)^{{N}} ⊢ ⌈NP⌉NP

((⌈det⌉(N→⌈NP⌉NP))det)^{{det}}, (Mann)^{{N}} ⊢ ⌈NP⌉NP

(⟨det⟩⌈det⌉(N→⌈NP⌉NP))^{{det}}, (Mann)^{{N}} ⊢ ⌈NP⌉NP

(der)^{{det}}, (Mann)^{{N}} ⊢ ⌈NP⌉NP

(derMann)^{L} ⊢ ⌈NP⌉NP
derMann ⊢ ⌈L⌉⌈NP⌉NP

see above derMann ⊢ ⌈L⌉⌈NP⌉NP

(derMann)NP ⊢ ⟨NP⟩⌈L⌉⌈NP⌉NP

{S ⊢ S \atop (⌈S⌉)S ⊢ S} ; ⌈S⌉S ⊢ ⌈S⌉S

(derMann)NP, ⟨NP⟩⌈L⌉⌈NP⌉NP→⌈S⌉S ⊢ ⌈S⌉S

(derMann)NP, (⌈v⌉(⟨NP⟩⌈NP⌉NP→⌈S⌉S))v ⊢ ⌈S⌉S

(derMann)NP, ((⌈v⌉(⟨NP⟩⌈NP⌉NP→⌈S⌉S))v)^{{v}} ⊢ ⌈S⌉S

(derMann)NP, (⟨v⟩⌈v⌉(⟨NP⟩⌈NP⌉NP→⌈S⌉S))^{{v}} ⊢ ⌈S⌉S

(derMann)NP, (läuft)^{{v}} ⊢ ⌈S⌉S

((derMann)NP)^{{NP}}, (läuft)^{{v}} ⊢ ⌈S⌉S

((derMann)NP läuft)^{L} ⊢ ⌈S⌉S

(derMann)NP läuft ⊢ ⌈L⌉⌈S⌉S

((derMann)NP läuft)S ⊢ ⟨S⟩⌈L⌉⌈S⌉S

8 Conclusion

I’ve shown how unary residuation can be used to model domain structure in a natural way. In a more serious grammar fragment than the one presented here, it may well happen that domain structure is a result of phenomena occurring in other dimensions than syntax, e.g. in phonology. In such a setting domains may no longer be accounted for by means of unary residuals, but rather be the result of constraints imposed by what happens in the other dimensions. In a multidimensional categorial grammar this will also be stated in terms of residuals. Due to the similarities between unary and binary residuals there may still be a close connection in such a calculus to the approach sketched in this paper.

Similar considerations apply to the account of LP constraints within the type logic. “What’s wrong with just imposing these constraints on the antecedents of sequents derivable in an undirected calculus” one might ask. The answer lies in the simplicity of the system presented here — or rather, in the putable intricacies of grammars for more serious fragments, where LP constraints may be dependent on the interaction of other dimensions of the grammar. It might be easier to adapt the present approach to such systems than it would be to derive linear order facts from the complex structures generated by them.

Finally, let me mention two directions for future research.

1. As I’ve shown in Section 5, modalised types can display quite subtle interactions. More subtle, in fact, than is needed to account for the phenomena discussed in the present paper. An obvious challenge is therefore an investigation of their other possible linguistic uses.

2. On a more technical note, the combination of an undirected calculus with LP constraints based on a partial order seems to be very close to Rétoré’s (1993) Pomset Logic. The precise nature of this connection remains to be seen, however.

References

[Bech, 1955] Gunnar Bech. Studien über das Deutsche Verbum Infinitum, volume 35(2) of Historisk-filologische Meddelelser. Det Kongelige Danske Videnskabernes Selskab, 1955.

[Došen, 1992] Kosta Došen. A brief survey of frames for the Lambek calculus. Zeitschrift für mathematische Logik und Grundlagen der Mathematik, 38:179–187, 1992.

[Girard, 1987] Jean-Yves Girard. Linear logic. Theoretical Computer Science, 50:1–102, 1987.

[Kurtonina and Moortgat, 1995] Natasha Kurtonina and Michael Moortgat. Structural control. In Patrick Blackburn and Maarten de Rijke, editors, Logic, Structures and Syntax. Reidel, Dordrecht, 1995.

[Kurtonina, 1995] Natasha Kurtonina. Frames and Labels. A Modal Analysis of Categorial Inference. PhD thesis, OTS Utrecht & ILLC Amsterdam, 1995.

[Moortgat and Oehrle, 1993] Michael Moortgat and Richard Oehrle. Adjacency, dependency and order. In Proceedings 9^{th} Amsterdam Colloquium, pages 447–466, 1993.

[Moortgat, 1995] Michael Moortgat. Multimodal linguistic inference. IGPL Bulletin, Special Issue on Deduction and Language, 3, 1995.

[Morrill et al., 1990] Glyn Morrill, Neil Leslie, Mark Hepple, and Guy Barry. Categorial deductions and structural operations. In Guy Barry and Glyn Morrill, editors, Studies in Categorial Grammar (Edinburgh Working Papers in Cognitive Science, Vol. 5), pages 1–21. Centre for Cognitive Science, University of Edinburgh, 1990. Edinburgh Working Papers in Cognitive Science 5.

[Morrill, 1990] Glyn Morrill. Intensionality and boundedness. Linguistics and Philosophy, 13:699–726, 1990.

[Pentus, 1992] Mati Pentus. Lambek grammars are context free. Ms. University of Moscow, 1992.

[Reape, 1992] Mike Reape. A Formal Theory of Word Order: A Case Study in West Germanic. PhD thesis, University of Edinburgh, 1992.

[Reape, 1994] Mike Reape. Domain union and word order variation in German. In John Nerbonne, Klaus Netter, and Carl Pollard, editors, German in Head-Driven Phrase Structure Grammar. University of Chicago Press, 1994. CSLI Lecture Note Series.

[Reape, to appear] Mike Reape. Getting things in order. In Arthur van Horck and Wietske Sijtsma, editors, Discontinuous Constituency. Mouton de Gruyter, Berlin, to appear.

[Rétoré, 1993] Christian Rétoré. Réseaux et Séquents Ordonnés. PhD thesis, Université Paris 7, 1993.

[Versmissen, 1995] Koen Versmissen. The conjoinability relation in categorial logics (ftp://ftp.let.ruu.nl/pub/users/versmissen/mol4.ps.gz). Ms. OTS, Utrecht, 1995.