Meaningful patterns

Michael Moortgat

Contents

1 Introduction  1
2 Linguistics 210  2
2.1 Verb final subordinate clauses . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Head adjunction: verb clusters . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 Verb initial clauses: yes/no questions . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4 Verb second: declarative main clauses . . . . . . . . . . . . . . . . . . . . . . . 12
2.5 Extraction: take-home assignment . . . . . . . . . . . . . . . . . . . . . . . . . 12
3 Conclusion  13
4 Screen shots from the computer lab  14

1 Introduction

Natural languages, in their individual ways, exploit patterns of grammatical form to convey the assembly of meaning. A central goal for linguistics is to find out in what respects languages are alike in this, and in what respects they can differ: in other words, to identify invariants in the composition of grammatical form and meaning, and to delineate the space for variation, allowing for the realization of the same meaning assembly through different structural patterns. Lambek’s categorial framework addresses the first of these questions: it provides a vocabulary of type-logical constants together with a proof-theoretic modeling of ‘grammatical computation’. But the original Lambek framework offers no tools for the analysis of structural variation: the structural properties of the constants are hard-wired. In this contribution, we explore two enhancements of the categorial architecture that bring the interplay between uniformity and variation into focus. First, we move from the one-dimensional world of Lambek calculus to a multimodal setting, where different composition operations live together and interact. The various modes of composition share the same base logic, but they can differ in their structural properties. Second, we introduce logical constants to control structural reasoning, thus replacing global structural regimes by lexically anchored local fine-tuning.^{1}

Johan van Benthem’s work has been vital in turning categorial grammar into a flexible tool for the analysis of linguistic form and meaning. With this contribution I would like to acknowledge a tremendous debt to his inspiring work. The material in §2 is based on joint work with Dick Oehrle.^{2} I have taken the presentation format from Lakatos’ engaging treatment of the ‘logic of mathematical discovery’.^{3} The methodological point of that book — that the field develops not through a monotonous accumulation of established truths, but through ‘the incessant improvement of guesses by speculation and criticism’ is very much in tune with Johan’s view on logical research^{4}, and very commendable when it comes to investigating the ‘logic of grammar’.

1See Chapter 2, Section 4 of the Handbook of Logic and Language (Van Benthem and ter Meulen (eds), Elsevier Science, 1997), and Kurtonina and Moortgat ‘Structural Control’ in Blackburn and de Rijke (eds.)

Specifying Syntactic Structures. CSLI, Stanford, 1997, 75–113.

2See our course at the ESSLLI99 summer school.

2 Linguistics 210

The discussion is set in a classroom. linguistics 210 is an obligatory course in the Adult Education Programme. It is a mixed class. Half of the pupils are generative linguists. They talk a lot about grammar as a ‘computational system’. But when asked to actually compute something, i.e. use an algorithm, they become evasive. The other half of the class consists of logicians. They have all heard about ‘Lambek calculus’. But their exposure to grammatical patterns of any significance has been limited. Not surprisingly, they feel highly reluctant to extend the analytical vocabulary beyond ‘slash’ and ‘backslash’. Fortunately for the teacher, the course comes with a nice software package.^{5}. While the discussion is going on, both the linguists and the logicians have a chance to actually gain some hands-on experience with grammatical modeling. The students are all actively participating, with the exception of epsilon, who has been complaining he does not see the point of taking the course since ‘everybody knows these categorial systems are just clumsy ways of doing context-free grammar’. He has been asked to take some screen shots of the computer lab exercises, and make himself useful that way.

teacher: Last week, we have been looking at the logical structure of linguistic theory. Here is a brief recap. The basic statements of our grammar logic are sequents Γ ⊢ A, asserting that the structure Γ is of type A. Formulas (types) are built from atoms p_{1}, p_{2}, … with the binary connectives /_{i}, •_{i}, \_{i} and the unary connectives ♢_{j}, □_{j}. Structures are built out of formulas with the operations (· ∘_{i} ·) and ⟨·⟩^{j}, structural counterparts of •_{i} and ♢_{j} respectively. The indices i and j are taken from given, finite sets I, J which we refer to as composition modes. The composition modes all share the same base logic, given by the residuation inferences of Fig 1.

\begin{matrix}♢_{j}A ⊢ B & iff & A ⊢ □_{j}B \\ A ⊢ C/_{i}B & iff & A •_{i} B ⊢ C & iff & B ⊢ A\_{i}C \end{matrix}

Figure 1: The base logic: residuation

But they can differ in the structural rules they allow. Structural rules take the form of axiom schemata A ⊢ B, where the input A is built out of distinct formula variables A_{1}, …, A_{n} purely in terms of ♢_{j} and •_{i}, and where the output B is a ♢_{j′}/•_{i′} formula constructed out of exactly the same A_{1}, …, A_{n}. The postulates are linear, in other words: they can rearrange grammatical material, but they cannot duplicate or waste it. Specifying a grammar, in the present setting, means giving a lexicon, i.e. an assignment of type formulas to the words, and specifying a set of structural rules, both relative to a selection of modes from I, J.

Today, to give you a better understanding of the interplay between logical and structural reasoning, I’d like to discuss a puzzle in the grammar of Dutch with you: the positioning of the verbal head for different clause types. half of the pupils: Oh no! Is this really necessary? the other half: It’s about time we get some data to look at! teacher: Alpha, you always have these impressive displays of example sentences in your term papers. Maybe you could give your colleagues a gentle introduction to the problem. Please keep it simple — just stick to the facts and give us some handy descriptive terminology that will facilitate the discussion. alpha [to his neighbour ]: ‘Stick to the facts’ — what a perverse attitude! The Teacher does not seem to understand that Progress replaces naive classification by theory-generated classification! But I want to get my grade for this course, so let me do what I am asked … [At the blackboard, addressing the class ] Look at the following groups of examples. In the (a) set, we have examples of subordinate clauses. I have underlined the verbal heads — they occur in clause-final position, following the complements. When you read in the literature on language typology that Dutch is an OV language (‘Objects-Verb’), this is the clause type one is referring to. Note also that the verbal head can be a simple tensed verb (the first two examples), or a cluster of verbs (the last two). These verbal clusters, arising in the so-called Verb Raising construction, play a crucial role in the argument that not all natural languages are context free.^{6}

3Imre Lakatos Proofs and Refutations. The Logic of Mathematical Discovery, Cambridge, 1976.

4See his ‘Logical semantics as an empirical science’ in Essays on Logical Semantics, Reidel, Dordrecht, 1986.

5Judging from the pictures we find in § 4, the class is using Richard Moot’s theorem prover Grail — no doubt an acronym for grammar = logic.

epsilon [sneering ]: Too bad for the Lambekians!

alpha [undisturbed ]: Now in non-subordinate clauses, the (tensed) verb occupies another position: compare (a) with (b) and (c). In the yes/no questions of (b), the tensed verb occurs clause-initially; in the declarative main clause (c), it takes the ‘second position’ — the position after the first major constituent, the subject, in a regular main clause.

a (… als) Alice de Soepschildpad \underline{plaagt}  subordinate clauses

(… als) Alice de koningin gek \underline{vindt}

(… of) Alice de Soepschildpad \underline{zou willen plagen} (… of) Alice de Soepschildpad \underline{probeert te plagen}

b \underline{Plaagt} Alice de Soepschildpad?  polar interrogatives

\underline{Vindt} Alice de koningin gek?

\underline{Zou} Alice de Soepschildpad willen plagen? \underline{Probeert} Alice de Soepschildpad te plagen?

c Alice \underline{plaagt} de Soepschildpad.  declarative main clauses

Alice \underline{vindt} de koningin gek.

Alice \underline{zal} de Soepschildpad willen plagen. Alice \underline{probeert} de Soepschildpad te plagen.

teacher: So we have three types of clauses— they are all assembled out of the same pieces, but the pieces are put together in different structural configurations. The challenge for our session today is to build a fragment that derives the different clausal types from one type assignment to the verbs, using structural reasoning. The approach I would like to explore with you can be called a ‘key-and-lock’ strategy. The strategy rests on two ideas. First, we distinguish the various clausal types by putting a control feature on the goal formula. In the table below, I have chosen mnemonic labels for the mode indices (e, i, 2 for end, initial and second position, respectively).

6Recommended reading for the class on this subject are Chapters 16 (Footloose and context-free) and 17 (Nobody goes around at LSA meetings offering odds) in Geoff Pullum’s The Great Eskimo Vocabulary Hoax, University of Chicago Press, 1991.

Γ ⊢ □_{e}s subordinate clause (verb final)
Γ ⊢ □_{i}s main clause, interrogative (verb initial)
Γ ⊢ □_{2}s main clause, declarative (verb second)

Figure 2: Goal formulas for main and subordinate clauses

Second, we assign the verbal heads in these clauses a type with a control box as the main connective — say □_{0} (The verbs, in their lexical type assignment, have no information as to what clause type they will be used in, so we need a fresh mode index here.) The verbs will have subcategorizational requirements, expressed in terms of the left and right implication connectives. But the □_{0} decoration acts as a lock: as long as the □_{0} connective has not been eliminated, the implications cannot be used. Unlocking □_{0} requires a matching ♢_{0} key, to be provided by (the residuals of) the control features on the goal formula. In order to establish the communication between ♢_{e}, ♢_{i}, ♢_{2} and the verbal lock, we will formulate postulates that inspect the different clausal patterns, making sure that the verb indeed occupies the required position.

beta: ‘Keys and locks’ — enough vague metaphors! Give us a derivation!

2.1 Verb final subordinate clauses

teacher: Before I can do that, we have to decide which position we take to be the canonical one for the basic lexical type assignment to the verbs. In your GIL course^{7}, you have been reading Jan Koster’s classical paper^{8} arguing forcibly that the subordinate clause is the canonical pattern: I suggest we take this as our starting position, and have verbs select their complements to the left, accordingly.

zeta: But, Sir! You cannot be serious…

teacher [interrupting]: Yes, Zeta, I know: current teaching has it that Koster’s arguments do not count anymore, and that the English SVO pattern is universal. But for this to work, you need to introduce a generous supply of abstract syntactic positions^{9} for complements to move to. I think we agreed at the start of this course that this is not a legal move for the game we are playing: we do not have any autonomous ‘syntax’ generating ‘positions’ — structural patterns arise in the deductive process of deriving a goal formula from the type formulas of the lexical assumptions.

zeta [aside]: No functional projections? They seem to be taking minimalism a bit too seriously here.

teacher: Let us see now how we can implement the idea of checking the (clause final) position of the verb explicitly. Our goal here is to derive a sequent Γ ⊢ □_{e}s, in other words, to determine whether the structure Γ is indeed a verb final clause. Somewhere within Γ, we have the head verb, locked by the □_{0} feature. The postulate package in Fig 3 establishes the communication between □_{e} on the goal formula, and the lexical □_{0} decoration. P 1 allows the messenger ♢_{e} to recursively traverse phrasal structure, looking for the verbal head on the right branch. When the recursion bottoms out, the control switches from ♢_{e} to ♢_{0} by means of P 2. You can find a derivation in Fig 9.

7‘Great Ideas in Linguistics’

8‘Dutch as an SOV language’, Linguistic Analysis 1 (1975), 111–136. Given the example sentences the class is using, the Dutch version may be more appropriate: ‘Het werkwoord als spiegelcentrum’, Spektator 3 (1974), 601–619.

9A conservative estimate for the structure of the functional domain would have the following spine of functional projections: CP-C’-AgrSP-TP-T-AgrOP(for IO)-AgrO’-AgrOP(for DO)-AgrO’-VP.

\begin{matrix}♢_{e}(A •_{1} B) ⊢ A •_{1} ♢_{e}B & P 1 \\ ♢_{e}A ⊢ ♢_{0}A & P 2 \end{matrix}

Figure 3: Verb final: subordinate clauses

beta: I think I understand what you meant with the ‘key-and-lock’ strategy. Provided that the messenger ♢_{e} indeed finds the head verb in clause final position, application of P 2 gives rise to a reduction ♢_{0}□_{0}A ⊢ A, which then unleashes the subcategorizational requirements of the verb.

teacher: Right. The way you formulate it, I see you’re really visualizing the derivation process in terms of a top-down, backward chaining Gentzen computation. But you could also take the bottom-up Natural Deduction perspective of Fig 9. Here you start the computation from the lexical assumptions — the leaves of the derivation tree. The part of the proof above the line (†)

(†) \begin{matrix}& •_{1} \\ Alice & •_{1} _{de koningin •_{1} ; _{gek \begin{matrix}♢_{0} \\ vindt \end{matrix}}} \end{matrix} ⊢ s  (‡) ♢_{e} •_{1} _{Alice •_{1} _{de koningin •_{1} ; _{gek vindt}}} ⊢ s

showns how far you can get with just the logical rules of inference: you eliminate the constants in the lexical type assignments. The sequence of structural inferences that follows then establishes the communication with (‡), the structure that yields the goal formula □_{e}s after one further logical step of [□I].

gamma: Before you all get carried away with this ‘key-and-lock’ game, could I bring it to your attention that the subordinate clause order is already derivable from the simple lexical assignment vindt ⊢ ap\(np\(np\s)), without any □ decoration or pushing around of ♢ marks: just Functional Application!

teacher: Looking just at the examples in this section (where the clause is projected from a simple tensed head verb), this is true. We decided to take the subordinate clause order as canonical, and the type assignment, with verbal complements under a left implication, reflects that. I wonder whether you will maintain your sceptical attitude vis à vis ♢, □ when we broaden the discussion to include subordinate clauses headed by verb clusters rather than simple verbal heads. Alpha, why don’t you…

2.2 Head adjunction: verb clusters

alpha: I take it you want me to give our logical friends here a little briefing as to what the relevant data are? [Sarcastically] In plain observational terms, of course! To keep things manageable, I suggest we restrict our attention to modal auxiliaries (wil, zal, moet …) and perception verbs (hoort, ziet, …) for a start. They subcategorize for a bare infinitival complement. Now consider the following examples.^{10}

dat Alice de Soepschildpad \underline{wil plagen} … wants to tease the Mock Turtle dat Alice de Soepschildpad \underline{wil kunnen plagen} … wants to be able to tease the Mock Turtle dat Alice de Soepschildpad een droevig lied \underline{hoort zingen} … hears the Mock Turtle sing a sad song

There are a number of things one can ‘observe’ about this composition pattern:

- Rather than combining with the complete infinitival complement, the modal axiliaries combine with the verbal head of the complement, passing over whatever complements this infinitival head itself may have. The resulting combination of verbal heads is what one usually refers to as the ‘verb cluster’ — I have underlined it in the examples above.

- The order of the verbs in a cluster gives rise to ‘crossing dependencies’, as you can see when you connect wil with its subject Alice, and plagen with its direct object de Soepschildpad.

- The formation of the verb cluster, with modal auxiliaries such as wil, …, is obligatory. Compare the ungrammatical example below with its English counterpart.

*dat Alice wil de Soepschilpad plagen that Alice wants to tease the Mock Turtle

teacher: Maybe we could challenge Gamma a little here, and see how far we can get without structural reasoning or control — just by solving plain Lambek type equations. Let’s run the Buszkowski-Penn typing algorithm^{11} on a sequence of verb phrases of growing complexity. In the input structures, the head of a configuration is the component pointed at by ◁/▷. You find the results in Fig 10. Any comments on the solutions for the aux element?

wil ◁ slapen ⊢ vp

de Soepschildpad ▷ (wil ◁ plagen) ⊢ vp

Alice ▷ (een taart ▷ (wil ◁ overhandigen))) ⊢ vp

beta: From a semantic point of view, one could say that the first verb-phrase displayed is optimal, in the sense that structural and semantic composition coincide. But in the input data that follow, there is a discrepancy between semantic composition (requiring the assembly of the infinitive and its complements, to produce the saturated infinitival phrase which aux selects for) and structural composition (requiring the adjunction of aux to the head of its infinitival complement). Our plain Lambek typing algorithm cannot resolve this discrepancy — the types assigned to aux do not unify, so one ends up with irreducible lexical polymorphism, it would seem.

alpha: Let me add that cluster formation is a recursive process. As the example with horen already suggests, there is in principle no bound on the number of complements a cluster may require: the perception verbs increment the arity of the cluster. Lexical ambiguity, in other words, would mean an infinite lexicon, in the limiting case. Now I thought you were so keen on characterizing a grammar as a (finite!) lexicon, closed under a number of generating functions — the rules of inference, in the case at hand.

10The discussion of verb clusters usually involves kraanvogels and nijlpaarden. We stick to the Lewis Carroll cast.

11Buszkowski and Penn, ‘Categorial grammars determined from linguistic data by unification’, Studia Logica, 49, 431–454.

gamma: OK — so I’d need some inductive type assignment schema for the triggers of verb cluster formation, in the sense of

(⋆) if aux ⊢ A/B then also aux ⊢ (C\A)/(C\B)

with aux ⊢ vp/inf as the boundary case. I see that a naive lexical look-up procedure leads to non-termination with such a schema. But I’m sure I could come up with a more sophisticated call-by-need technique that would keep the parsing algorithm decidable.^{12}

eta: I’m sorry to interrupt you. You are talking about ways of overcoming the expressive limitations of plain Lambek calculus in the light of verb cluster formation. But I’m afraid you’ll have to deal with a much more ugly problem first. I ran our theorem prover in the ‘Generate’ mode with the type assignment we got from Fig 10. As things stand, there is nothing that blocks the derivation of the ungrammatical ‘English’ order

*dat Alice wil de Soepschilpad plagen that Alice wants to tease the Mock Turtle dat Alice wil slapen that Alice wants to sleep

given the type assignment wil ⊢ vp/inf. Certainly that is a type assignment we’ll need for the combination with a simple infinitival complement!

teacher: Let me summarize this discussion. On the one hand, the plain Lambek grammar overgenerates, as Eta was careful to point out: blocking the combination of wil with an infinitive that is itself the result of a number of composition steps, as in the starred example above, requires control. On the other hand, with just logical rules of inference, our Lambek grammar is too weak to establish the proper form-meaning correspondence for the verb clusters: we’d like to license structural reasoning, in order to resolve the discrepancy between the composition of grammatical form and meaning assembly.

To start with the second point: Gamma just proposed an inductive type assignment schema (⋆) to obtain the infinite set of possible types for an aux element from a ‘basic’ assignment. Such a lexical type assignment schema, as it stands, is external to the grammar logic proper. What we are looking for here is the right mixture of logical and structural reasoning that would enhance our proof-theoretic engine in such a way that the type transitions licensed by (⋆) can be computed on-line. I am sure Beta has ideas about this.

beta: Well, if I take the combined top-down/bottom-up approach we discussed a moment ago, the situation is as follows. The top line of the derivation below is obtained in terms of bottom-up Modus Ponens steps. Conditional reasoning, in backward chaining fashion, allows me to transform the complex goal formula into a structure term.

⋮

vp/inf • (obj • obj\inf) ⊢ vp

\, /E

obj • (vp/inf • obj\inf) ⊢ vp

structural pattern matching?

vp/inf • obj\inf ⊢ obj\vp

\I

vp/inf ⊢ (obj\vp)/(obj\inf)

/I

12Maybe Gamma is thinking of something like the techniques for delayed evaluation worked out in Bouma and Van Noord’s ‘Constraint-based categorial grammar’.

At the point where the logical inferences halt, I can now solve a structural equation (just as we were solving logical type equations before). The pattern matching that establishes the communication between the two terms involved, yields the structural postulate:

(†) A • (B • C) ⊢ B • (A • C)

teacher: Now for some structural fine-tuning! You realize that in the one-dimensional Lambek world, with just a single composition operation •, your postulate causes fatal damage to order-sensitivity. But in the multimodal setting, we can refine the signature, and formulate (†) as an interaction principle, relating two distinct composition modes: our familiar •_{1} for regular phrasal complementation, and a mode •_{0} which we’ll use to type the triggers of verb cluster formation.

(‡) A •_{1} (B •_{0} C) ⊢ B •_{0} (A •_{1} C)

eta: I can see how this interaction postulate allows you to derive the cluster wil plagen below, from lexical assumptions wil ⊢ vp/_{0}inf and plagen ⊢ np\_{1}inf. And I also see how it avoids the unwanted scrambling effects of one-dimensional (†). But what about the problem I just brought up? With (‡), your grammar still accepts the ungrammatical ‘English’ order — as a matter of fact, the structural configuration of the starred example below serves as the premise for the (‡) step. Surely, there is nothing in the logic that forces you to make the structural move!

als Alice de Soepschildpad wil plagen *als Alice wil de Soepschildpad plagen

teacher: I think we have reached the point where you’ll come to appreciate the control devices ♢, □. With the help of these connectives we can achieve exactly what Eta is alluding to: they provide logical means of forcing the composition of the verb cluster, rather than just allowing it to come into being. Let us go back to our earlier decision to ‘lock’ verbal heads with a □_{0} feature, and consider the structural configuration of the end sequent we want to derive:

Alice ((de soepschildpad) (wil ∘_{0} plagen)) ⊢ □_{e}s

We have seen already how P 1 and P 2 localize the verbal head in its clause final position. But now, instead of finding a simple verb there, the ♢_{0} messenger is confronted with a verbal cluster. By strongly distributing ♢_{0} over •_{0}, Postulate P 3 checks whether indeed the components of such a cluster are both verbal heads, and whether they are put together in the •_{0} mode. And we can improve on (‡) too, by lexically anchoring this structural inference, so that it has to be explicitly licensed by the ‘verbal head’ feature ♢_{0}. This yields P 4 as a controlled form of (‡). The postulate will be called now from a lexical type assignment wil ⊢ □_{0}(vp/_{0}inf). Have a look at the derivation in Fig 11.

\begin{matrix}♢_{0}(A •_{0} B) ⊢ ♢_{0}A •_{0} ♢_{0}B & P 3 \\ A •_{1} (♢_{0}B •_{0} C) ⊢ ♢_{0}B •_{0} (A •_{1} C) & P 4 \end{matrix}

Figure 4: Verb cluster formation: clause union

eta: So your claim is that these postulates actually force the formation of the verb cluster, making the ungrammatical ‘English’ order underivable, as we wanted? Let me think … [Silence] I see it! We have two verbal heads in this clause — two □_{0} locks, in other words. The goal formula □_{e}s provides only one key. The only way to duplicate the ♢_{0} key is by means of P 3.

But that implies that P 2 must already have switched the control from ♢_{e} to ♢_{0}. The P 2 move is irreversible, but once we have ♢_{0}, the control feature does not distribute through phrasal •_{1} structure any more. It’s surprising, but it seems this utterly simple package actually gives us a grammar of clause union!

teacher [aside]: I am not sure everybody here shares Eta’s enthousiasm about the simplicity. [To the class again] Well, utter simplicity… This was just a first stab. Maybe someone else has a more simple solution to our little structural puzzle?

delta: I am not sure my solution is more simple, but I think it is certainly not inferior to what you just presented. Your lexical assignment has the the key verbs (willen, horen, etc) select their complement to the right. Instead, in my fragment they select their complement infinitive to the left: schematically, my lexicon has □_{0}(B\_{0}A) where you have □_{0}(A/_{0}B). The structural package, for my solution, replaces P 3, P 4 by the postulates below.

\begin{matrix}P 3′ : & ♢_{0}(A •_{0} B) ⊢ ♢_{0}B •_{0} ♢_{0}A \\ P 4′ : & A •_{1} (B •_{0} ♢_{0}C) ⊢ (A •_{1} B) •_{0} ♢_{0}C \end{matrix}

P 3′ recursively ‘unwinds’ the crossing dependencies of the verbal cluster. The mixed associativity law P 4′ changes the dominance relation between •_{1} and •_{0}, giving the latter the appropriate scope for meaning assembly. Compare the derivation in Fig 14 with that of Fig 11. Below, you see the different structural rewritings in schematic form:

•_{1}
object ♢_{0} ; \begin{matrix}•_{0} \\ □_{0}aux & □_{0}tv \end{matrix}

⟶^{P 3} •_{1}

object \begin{matrix}•_{0} \\ \begin{matrix}♢_{0} \\ □_{0}aux \end{matrix} & \begin{matrix}♢_{0} \\ □_{0}tv \end{matrix} \end{matrix}

⟶^{P 4} •_{0}

\begin{matrix}♢_{0} \\ □_{0}aux \end{matrix} •_{1}

object \begin{matrix}♢_{0} \\ □_{0}tv \end{matrix}

•_{1}
object ♢_{0} ; \begin{matrix}•_{0} \\ □_{0}aux & □_{0}tv \end{matrix}

⟶^{P 3′} •_{1}

object \begin{aligned}& •_{0} \\ \begin{matrix}♢_{0} \\ □_{0}tv \end{matrix} & \begin{matrix}♢_{0} \\ □_{0}aux \end{matrix} \end{aligned}

⟶^{P 4′} •_{0}

•_{1}
object \begin{matrix}♢_{0} \\ □_{0}tv \end{matrix}

\begin{matrix}♢_{0} \\ □_{0}aux \end{matrix}

beta: I don’t understand how you arrive at the lexical type assignments □_{0}(B\_{0}A). Structurally, the lexical items in question appear as prefixes to the infinitives they combine with — how would the Buszkowski-Penn typing algorithm ever come up with a left implication?

delta: I see what you mean. But I can streamline my lexicon, expressing the pleasant generalization that Dutch verbs select their complements uniformly to the left. Our discussion here has been focusing heavily on squeezing out structural generalizations at the level of the ‘computational system’ — translating Gamma’s lexical type assignment schema (⋆) into online structural reasoning, for example. But in the end, when it comes to measuring overall simplicity of a grammar, I think we should attach equal weight to generalizations at the level of the lexicon — constraints on the shape of lexical type assignments, for example, that restrict the space for such assignments to a proper subsystem of the full formula language.

alpha: That sounds like a valid methodological advice. But even at a more down-to-earth level, if you broaden the range of data under consideration a little, you will see that Delta has a point. Take the pronominal forms of infinitival complements: they are selected to the left. omdat Alice de Soepschildpad wil plagen omdat Alice dat (=de Soepschildpad plagen) wil

With the P 3/P 4 approach, not only would you have non-uniformity in the directionality of complement selection (leftward for some verbs, to the right for others), but the □_{0}(A/_{0}B) type verbs that give rise to cluster formation need an extra assignment for pronominal realizations of their complements.

teacher: You seem to be preparing us for a choice between Delta’s P 3′/P 4′ solution (and the lexical assignments that go with it) and the P 3/P 4 alternative, Delta coming out as the winner. But we could also take a more liberal attitude. I agree that the P 3/P 4 lexicon is slightly suboptimal as compared to Delta’s. But this is an innocent form of lexical ambiguity — altogether different from Gamma’s (⋆) schema, where missing the structural generalization inflates the lexicon up to infinity. I’d say the two solutions are roughly of the same complexity. Now, suppose we say the goal of our game (formulating a fragment, in your case, or learning the language, for LAD) is to compute the appropriate form-meaning correspondences for Dutch. Then the two solutions can both count as successful. The grammars in Delta’s head and in mine, in other words, could have different solutions for the logical type equations and the structural equations for the language in question — as long as these solutions associate the same forms with the same meanings, they would count as equally good.

But we’ve been talking about the subordinate clause long enough now. I think we should return to the main theme, and see how we can relate verb positioning for the different clausal types.

gamma: We are all ears.

2.3 Verb initial clauses: yes/no questions

teacher: Let us start with the verb initial main clause type □_{i}s. We saw that polar interrogatives (yes/no questions) exemplify □_{i}s in its simplest form. Yes/no question have an intonational contour (marked by ‘?’ in writing) that distinguishes them from declarative clauses. We could assign ‘?’ the type □_{i}s\_{1}q, with an appropriate denotation type for question semantics for the basic type q. But today, we’ll focus on the syntax of the □_{i}s part.

Plaagt Alice de Soepschildpad? Vindt Alice de Koningin gek? Probeert Alice de Soepschildpad te kunnen vergeten?

The challenge in dealing with □_{i}s is to establish a derivational relationship between verbal types in their canonical clause final position and in the fronted, clause initial position required for □_{i}s. I suggest we approach this problem in stages, as we did in discussing the subordinate clause. Let us look first at the fronting of simple tensed verbs, and then turn to verb fronting out of verb clusters. The control strategy can be essentially the same as for the treatment of subordinate clauses: we have to establish communication between □_{i} on the goal formula, and the □_{0} lock on the verbal head of the clause — in doing so, the diamond messenger has to make sure that the clause is indeed verb initial. Who wants to try?

kappa: Well, there is a difference with the ‘passive’ inspection of structure of P 1/P 2: in the case of □_{i}s, the head verb cannot be actually used in its initial position: it has to be manoeuvred into the canonical clause final position. My solution is in Fig 5.

As you see, I haven’t been able to manage just with ♢_{i} and ♢_{0}: the signature of my fragment introduces an in-between unary mode j. Postulate P 5 works on the assumption that the clause indeed starts with the verb, which it moves back to clause final position, marking it

\begin{matrix}♢_{i}(A •_{1} B) ⊢ B •_{1} ♢_{j}A & P 5 \\ (A •_{1} B) •_{1} ♢_{j}C ⊢ A •_{1} (B •_{1} ♢_{j}C) & P 6 \\ ♢_{j}A ⊢ ♢_{0}A & P 7 \end{matrix}

Figure 5: Verb initial. (to be cont’d)

with a ♢_{j} control feature. Notice that P 5 is a once-only, non-recursive structural inference. P 6 then ‘lowers’ the verb into the verb phrase, to the appropriate level of embedding where, with the help of P 7, it can be unlocked in its canonical position. You can view a sample derivation in Fig 15. The structural inferences, again, mediate between the canonical part of the proof (logical inferences only) and the structure required by the □_{i}s goal formula.

teacher: Good. But what about the interrogatives below, where the fronted verb is part of a verb cluster in the subordinate counterpart?

Wil Alice de Soepschildpad plagen?

vs als Alice de Soepschildpad wil plagen

Probeert Alice de Soepschildpad te plagen?

vs als Alice de Soepschildpad probeert te plagen

beta: Let me try to narrow down the problem via the combined top-down/bottom up strategy we used before. Reasoning backwards from the conclusion, postulates P 5, P 6 bring us as far as the bottom line of the derivation below. We have to formulate a structural inference that establishes the communication between the bottom line and the part of the derivation which, with the help of P 7, feeds into a structure from which the canonical clause-final order of the verb cluster can be computed.

(cf Fig 11) Alice ∘_{1} (de Soepschildpad ∘_{1} ⟨wil ∘_{0} plagen⟩^{0}) ⊢ s

Alice ∘_{1} (de Soepschildpad ∘_{1} ⟨wil ∘_{0} plagen⟩^{j}) ⊢ s

P 7

Alice ∘_{1} (de Soepschildpad ∘_{1} (plagen ∘_{1} ⟨wil⟩^{j})) ⊢ s

structural inference?

gamma: The straightforward answer is P 7′: it introduces •_{0}, the mode for verb cluster formation, and it feeds into P 7, which in turn communicates with the strong distributivity postulate P 3.

P 7′ A •_{1} ♢_{j}B ⊢ ♢_{j}(B •_{0} A)

If you agree that the rewriting sequence P 7′ ⇝ P 7 ⇝ P 3 will always occur en bloc, we can speed up the derivation by using a well-known program transformation technique: we can ‘telescope’ this sequence into a one-step structural inference, P 7′′. A derivation which the compiled structural inference is displayed in Fig 16.

A •_{1} ♢_{j}B ⊢ ♢_{0}A •_{0} ♢_{0}B P 7′′

Figure 6: Fronting out of verb cluster. (Add to Fig 5)

eta: I hate to interrupt you again. But running our theorem prover in ‘Generate’ mode, I see that nothing blocks fronting of the complete verb cluster, rather than just the finite head:

*Wil plagen Alice de Soepschildpad?

vs Wil Alice de Soepschildpad plagen?

teacher: Now this problem is very similar to what we saw before, when we had to block the derivation of the ungrammatical ‘English’ order in subordinate clauses. I think adjusting the package P 5 − P 8 in the required way will make a very nice question for the written exam!

2.4 Verb second: declarative main clauses

teacher: That brings us to the final major clausal type on our agenda: the declarative main clause, with goal type □_{2}s. The tensed head verb of a declarative sentence occupies second position, following the subject.^{13} Compare the examples below with what we have seen before.

Alice plaagt de Soepschildpad. Alice vindt de koningin gek. Alice zal de Soepschildpad willen plagen. Alice probeert de Soepschildpad te plagen.

kappa: After the work I’ve done for □_{i}, the structural control package for verb second is really very simple: in the nonrecursive postulate P 8, the control operator ♢_{2} skips the first constituent of the clause it is in construction with, transmitting ♢_{i} (verb initial) control to the remainder of the clause. See Fig 17 for an example.

♢_{2}(A •_{1} B) ⊢ A •_{1} ♢_{i}B P 8

Figure 7: Verb second: main clauses

2.5 Extraction: take-home assignment

teacher: At this point, I would have liked to investigate with you how verb positioning interacts with the formation of relative clauses, and with subordinate and main clause questions. But I see it is time already for your next class. As a take-home assignment, I propose you extend the fragments we have been discussing with the following clause types.

a de Soepschildpad \underline{die} Alice probeert te plagen (relative clause)
b (Alice weet) \underline{wie} de koningin gek vindt  (subordinate question)
c \underline{Wie} wil de taarten stelen?  (main clause question)

Your task is twofold: provide type assignments for the new lexical items (underlined in the examples above): relative pronouns like die, subordinate or main clause question pronouns like wie, and specify the new structural inferences (if any) keyed to these type assignments. Here are some facts your type assignments will have to take into account, and some hints. (I am calling the material following these pronouns the body — of the relative clause, subordinate or main clause question, respectively).

13What we say here does not apply to ‘topicalized’ sentences, such as ‘De SOEPSCHILDPAD zal Alice willen plagen’, which are distinguished from declaratives by their prosodic realisation, and which would thus receive their own clausal type.

- With respect to verb positioning, the body of relative clauses and subordinate questions is of the □_{e}s type: the verb (cluster) occurs in clause-final position; the main clause question body is verb initial — type □_{i}s.

- In (a), (b) and (c) above, the body is not a complete clause (of type □_{e}s or □_{i}s), but a clause from which a noun phrase is missing. Use conditional reasoning (with respect to a np resource) to make sure the body constituents are not overcomplete.

- The pronouns are not specific as to what noun phrase hypothesis in the body they are withdrawing when reasoning: (a) and (b), for example, are ambiguous between a subject and an object hypothesis. Characterize the ‘accessible’ positions for hypothetical reasoning in terms of controlled structural inferences.

3 Conclusion

The slogans ‘Parsing = Deduction, Grammar = Proof Theory’^{14} rest on the assumption that mathematical logic offers appropriate tools for modeling the cognitive abilities underlying knowledge and use of language, and language acquisition. Can logic indeed provide an insightful explanation of linguistic cognition, or is its role limited to the level of ‘mere descriptive adequacy’? The answer to this question depends very much on the kind of logic one uses in grammatical analysis. When in the middle of the 17th century, Newton and Leibniz invented the calculus, they introduced a ‘new’ mathematical language — a language with the right expressive power for the analysis of motion and change, dynamic processes that had come to occupy a central position on the agenda of physics. The framework of substructural logic, in a similar spirit, turns out to provide appropriate instruments for reasoning about grammatical resources, and the dynamics of the assembly of grammatical form and meaning. Cross-linguistic invariants in the form-meaning correspondence are captured in terms of the proof-theoretic interpretation of the grammatical constants. The dimensions for structural variation are charted by complementing the logical core of the computational system with controlled structural reasoning.

14See Van Benthem Language in Action: Categories, Lambdas and Dynamic Logic North-Holland, Amsterdam, (Studies in Logic, vol. 130). Paperback reprint with new Appendix, The MIT Press, 1995.

4 Screen shots from the computer lab

♢_{0} verbal head
♢_{e} control: verb final
♢_{i}, ♢_{j} control: verb initial
♢_{2} control: verb second
•_{1} phrasal composition
•_{0} head adjunction (clause union)

Figure 8: Signature: mode distinctions for major clausal types.

of ⊢ x/□_{e}s

alice ⊢ np

de ⊢ np/n koningin ⊢ n de koningin ⊢ np [/E]

gek ⊢ ap vindt ⊢ □_{0}(ap\(np\(np\s))) ⟨vindt⟩^{0} ⊢ ap\(np\(np\s)) [□E]

gek ⟨vindt⟩^{0} ⊢ np\(np\s) [\E]

(de koningin) (gek ⟨vindt⟩^{0}) ⊢ np\s

[\E]

alice ((de koningin) (gek ⟨vindt⟩^{0})) ⊢ s

[\E]

alice ((de koningin) (gek ⟨vindt⟩^{e})) ⊢ s

[P 2]

alice ((de koningin) ⟨gek vindt⟩^{e}) ⊢ s

[P 1]

alice ⟨(de koningin) (gek vindt)⟩^{e} ⊢ s

[P 1]

⟨alice ((de koningin) (gek vindt))⟩^{e} ⊢ s

[P 1]

alice ((de koningin) (gek vindt)) ⊢ □_{e}s

[□I]

of (alice ((de koningin) (gek vindt))) ⊢ x

[/E]

Figure 9: Example: verb final. Here and below, for legibility the subscripts for the ‘default’ phrasal composition mode •_{1} in the type formulas are dropped. In the antecedent structure term, we omit ∘_{1} altogether, and use minimal bracketing to indicate grouping. The scope of the structural ⟨·⟩ operator is indicated by means of color coding.

\begin{aligned}& ◁ \\ aux & & inf \end{aligned} ▷

obj ◁ ; _{aux obj\inf}

▷ _{_{obj_{1}} ▷ _{_{obj_{2}} ◁ _{aux obj_{2}\(obj_{1}\inf)}}} etc

aux ⊢ vp/inf aux ⊢ (obj\vp)/(obj\inf), aux ⊢ (obj_{2}\(obj_{1}\vp))/(obj_{2}\(obj_{1}\inf))

Figure 10: Solving type equations

als ⊢ als/□_{e}s

alice ⊢ np

{wil ⊢ □_{0}((np\s)/_{0}inf) \atop ⟨wil⟩^{0} ⊢ (np\s)/_{0}inf} [□E]

de ⊢ np/n soepschildpad ⊢ n de soepschildpad ⊢ np [/E] plagen ⊢ □_{0}(np\inf) ⟨plagen⟩^{0} ⊢ np\inf [□E]

(de soepschildpad) ⟨plagen⟩^{0} ⊢ inf

[\E]
⟨wil⟩^{0} ∘_{0} ((de soepschildpad) ⟨plagen⟩^{0}) ⊢ np\s

[/E]

alice (⟨wil⟩^{0} ∘_{0} ((de soepschildpad) ⟨plagen⟩^{0})) ⊢ s

[\E]

alice ((de soepschildpad) (⟨wil⟩^{0} ∘_{0} ⟨plagen⟩^{0})) ⊢ s

[P 4]

alice ((de soepschildpad) ⟨wil ∘_{0} plagen⟩^{0}) ⊢ s

[P 3]

alice ((de soepschildpad) ⟨wil ∘_{0} plagen⟩^{e}) ⊢ s

[P 2]

alice ⟨(de soepschildpad) (wil ∘_{0} plagen)⟩^{e} ⊢ s

[P 1]

⟨alice ((de soepschildpad) (wil ∘_{0} plagen))⟩^{e} ⊢ s

[P 1]

alice ((de soepschildpad) (wil ∘_{0} plagen)) ⊢ □_{e}s

[□I]

als (alice ((de soepschildpad) (wil ∘_{0} plagen))) ⊢ als

[/E]

Figure 11: Example: verb cluster

\begin{matrix}1. & np − y_{0} & Lex \\ 2. & np/_{1}n − z_{0} & Lex \\ 3. & n − x_{1} & Lex \\ 4. & np − z_{0}(x_{1}) & /E (2, 3) \\ 5. & □_{0}(np\_{1}inf) − z_{1} & Lex \\ 6. & np\_{1}inf −^{∨}z_{1} & □E (5) \\ 7. & inf − (^{∨}z_{1} z_{0}(x_{1})) & \E (4, 6) \\ 8. & □_{0}((np\_{1}s)/_{0}inf) − y_{1} & Lex \\ 9. & (np\_{1}s)/_{0}inf −^{∨}y_{1} & □E (8) \\ 10. & np\_{1}s − (^{∨}y_{1} (^{∨}z_{1} z_{0}(x_{1}))) & \E (7, 9) \\ 11. & s − ((^{∨}y_{1} (^{∨}z_{1} z_{0}(x_{1}))) y_{0}) & \E (1, 10) \\ 12. & □_{e}s −^{∧}((^{∨}y_{1} (^{∨}z_{1} z_{0}(x_{1}))) y_{0}) & □I (11) \end{matrix}

Figure 12: Meaning assembly. Proof term for the □_{e}s subderivation. Term constructors and destructors for the logical Introduction and Elimination steps. The structural inferences leave the proof term unchanged.

1. np − alice  Lex
2. np/_{1}n − λx_{2}.(ιy_{2}x_{2}(y_{2}))  Lex
3. n − λz_{2}.mock(turtle(z_{2}))  Lex
4. np − ιy_{2}mock(turtle(y_{2}))  /E (2, 3)
5. □_{0}(np\_{1}inf) −^{∧}tease  Lex
6. np\_{1}inf − tease  □E (5)
7. inf − tease(ιy_{2}mock(turtle(y_{2})))  \E (4, 6)
8. □_{0}((np\_{1}s)/_{0}inf) −^{∧}(λx_{3}.(λy_{3}.^{∨}want(y_{3}, x_{3})))  Lex
9. (np\_{1}s)/_{0}inf − λx_{3}.(λy_{3}.^{∨}want(y_{3}, x_{3}))  □E (8)
10. np\_{1}s − λy_{3}.^{∨}want(y_{3}, tease(ιy_{2}mock(turtle(y_{2})))) \E (7, 9)
11. s −^{∨}want(alice, tease(ιy_{2}mock(turtle(y_{2}))))  \E (1, 10)
12. □_{e}s − want(alice, tease(ιy_{2}mock(turtle(y_{2}))))  □I (11)

Figure 13: Meaning assembly. Substitution of lexical semantics in the proof-term, with on-the-fly conversion. The lexical meaning programs for plagen (line 5) and wil (line 8) have a leading ∧ to ‘erase’ the Elimination trace of the □_{0} control operators. The program for wil, moreover, has a leading ^{∨} on the body of the term which cancels the Introduction trace of □_{e}.

als ⊢ als/□_{e}s alice ⊢ np

de ⊢ np/n soepschildpad ⊢ n de soepschildpad ⊢ np [/E] plagen ⊢ □_{0}(np\inf) ⟨plagen⟩^{0} ⊢ np\inf [□E]

(de soepschildpad) ⟨plagen⟩^{0} ⊢ inf [\E] {wil ⊢ □_{0}(inf\_{0}(np\s)) \atop ⟨wil⟩^{0} ⊢ inf\_{0}(np\s)} [□E]

((de soepschildpad) ⟨plagen⟩^{0}) ∘_{0} ⟨wil⟩^{0} ⊢ np\s

[\E]

alice (((de soepschildpad) ⟨plagen⟩^{0}) ∘_{0} ⟨wil⟩^{0}) ⊢ s

[\E]

alice ((de soepschildpad) (⟨plagen⟩^{0} ∘_{0} ⟨wil⟩^{0})) ⊢ s

[P 4′]

alice ((de soepschildpad) ⟨wil ∘_{0} plagen⟩^{0}) ⊢ s

[P 3′]

alice ((de soepschildpad) ⟨wil ∘_{0} plagen⟩^{e}) ⊢ s

[P 2]

alice ⟨(de soepschildpad) (wil ∘_{0} plagen)⟩^{e} ⊢ s

[P 1]

⟨alice ((de soepschildpad) (wil ∘_{0} plagen))⟩^{e} ⊢ s

[P 1]

alice ((de soepschildpad) (wil ∘_{0} plagen)) ⊢ □_{e}s

[□I]

als (alice ((de soepschildpad) (wil ∘_{0} plagen))) ⊢ als

[/E]

Figure 14: Example: verb cluster, Delta’s solution

alice ⊢ np de ⊢ np/n koningin ⊢ n de koningin ⊢ np [/E]

gek ⊢ ap vindt ⊢ □_{0}(ap\(np\(np\s))) ⟨vindt⟩^{0} ⊢ ap\(np\(np\s)) [□E]

gek ⟨vindt⟩^{0} ⊢ np\(np\s) [\E]

(de koningin) (gek ⟨vindt⟩^{0}) ⊢ np\s

[\E]

alice ((de koningin) (gek ⟨vindt⟩^{0})) ⊢ s

[\E]

alice ((de koningin) (gek ⟨vindt⟩^{j})) ⊢ s

[P 7]

alice (((de koningin) gek) ⟨vindt⟩^{j}) ⊢ s

[P 6]

(alice ((de koningin) gek)) ⟨vindt⟩^{j} ⊢ s

[P 6]

⟨vindt (alice ((de koningin) gek))⟩^{i} ⊢ s

[P 5]

vindt (alice ((de koningin) gek)) ⊢ □_{i}s

[□I]

Figure 15: Verb fronting for polar interrogatives. Kappa’s solution.

A. ⊢ np

de ⊢ np/n koningin ⊢ n de koningin ⊢ np [/E] plagen ⊢ □_{0}(np\inf) ⟨plagen⟩^{0} ⊢ np\inf [□E]

(de koningin) ⟨plagen⟩^{0} ⊢ inf [\E] {te ⊢ □_{0}(inf\_{0}te) \atop ⟨te⟩^{0} ⊢ inf\_{0}te} [□E]

((de koningin) ⟨plagen⟩^{0}) ∘_{0} ⟨te⟩^{0} ⊢ te

[\E]

probeert ⊢ □_{0}(te\_{0}(np\s)) ⟨probeert⟩^{0} ⊢ te\_{0}(np\s) [□E]

(((de koningin) ⟨plagen⟩^{0}) ∘_{0} ⟨te⟩^{0}) ∘_{0} ⟨probeert⟩^{0} ⊢ np\s

[\E]

A. ((((de koningin) ⟨plagen⟩^{0}) ∘_{0} ⟨te⟩^{0}) ∘_{0} ⟨probeert⟩^{0}) ⊢ s

[\E]

A. (((de koningin) (⟨plagen⟩^{0} ∘_{0} ⟨te⟩^{0})) ∘_{0} ⟨probeert⟩^{0}) ⊢ s

[P 4′]

A. (((de koningin) ⟨te ∘_{0} plagen⟩^{0}) ∘_{0} ⟨probeert⟩^{0}) ⊢ s

[P 3′]

A. ((de koningin) (⟨te ∘_{0} plagen⟩^{0} ∘_{0} ⟨probeert⟩^{0})) ⊢ s

[P 4′]

A. ((de koningin) ((te ∘_{0} plagen) ⟨probeert⟩^{j})) ⊢ s

[P 7′′]

A. (((de koningin) (te ∘_{0} plagen)) ⟨probeert⟩^{j}) ⊢ s

[P 6]

(A. ((de koningin) (te ∘_{0} plagen))) ⟨probeert⟩^{j} ⊢ s

[P 6]

⟨probeert (A. ((de koningin) (te ∘_{0} plagen)))⟩^{i} ⊢ s

[P 5]

probeert (A. ((de koningin) (te ∘_{0} plagen))) ⊢ □_{i}s

[□I]

Figure 16: Fronting out of verb clusters. Gamma’s P 7′′ as compilation-by-partial-execution.

alice ⊢ np

de ⊢ np/n soepschildpad ⊢ n de soepschildpad ⊢ np [/E] plagen ⊢ □_{0}(np\inf) ⟨plagen⟩^{0} ⊢ np\inf [□E]

(de soepschildpad) ⟨plagen⟩^{0} ⊢ inf [\E] {wil ⊢ □_{0}(inf\_{0}(np\s)) \atop ⟨wil⟩^{0} ⊢ inf\_{0}(np\s)} [□E]

((de soepschildpad) ⟨plagen⟩^{0}) ∘_{0} ⟨wil⟩^{0} ⊢ np\s

[\E]

alice (((de soepschildpad) ⟨plagen⟩^{0}) ∘_{0} ⟨wil⟩^{0}) ⊢ s

[\E]

alice ((de soepschildpad) (⟨plagen⟩^{0} ∘_{0} ⟨wil⟩^{0})) ⊢ s

[P 4′]

alice ((de soepschildpad) (plagen ⟨wil⟩^{j})) ⊢ s

[P 7′′]

alice (((de soepschildpad) plagen) ⟨wil⟩^{j}) ⊢ s

[P 6]

alice ⟨wil ((de soepschildpad) plagen)⟩^{i} ⊢ s

[P 5]

⟨alice (wil ((de soepschildpad) plagen))⟩^{2} ⊢ s

[P 8]

alice (wil ((de soepschildpad) plagen)) ⊢ □_{2}s

[□I]

Figure 17: Verb second: main clauses