A Logical Basis for the D Combinator and Normal Form in CCG

Frederick Hoyt and Jason Baldridge The Department of Linguistics The University of Texas at Austin {fmhoyt,jbaldrid}@mail.utexas.edu

Abstract
The standard set of rules defined in Combinatory Categorial Grammar (CCG) fails to provide satisfactory analyses for a number of syntactic structures found in natural languages. These structures can be analyzed elegantly by augmenting CCG with a class of rules based on the combinator D (Curry and Feys, 1958). We show two ways to derive the D rules: one based on unary composition and the other based on a logical characterization of CCG's rule base (Baldridge, 2002). We also show how Eisner's (1996) normal form constraints follow from this logic, ensuring that the D rules do not lead to spurious ambiguities.

that even with its flexibility, CCG as standardly defined is not permissive enough for certain linguistic constructions and greater incrementality. Following Wittenburg (1987), we remedy this by adding a set of rules based on the D combinator of combinatory logic (Curry and Feys, 1958).
(1) x/(y/z) : f y/w : g  x/(w/z) : h.f (x.g hx)

1

Introduction

Combinatory Categorial Grammar (CCG, Steedman (2000)) is a compositional, semantically transparent formalism that is both linguistically expressive and computationally tractable. It has been used for a variety of tasks, such as wide-coverage parsing (Hockenmaier and Steedman, 2002; Clark and Curran, 2007), sentence realization (White, 2006), learning semantic parsers (Zettlemoyer and Collins, 2007), dialog systems (Kruijff et al., 2007), grammar engineering (Beavers, 2004; Baldridge et al., 2007), and modeling syntactic priming (Reitter et al., 2006). A distinctive aspect of CCG is that it provides a very flexible notion of constituency. This supports elegant analyses of several phenomena (e.g., coordination, long-distance extraction, and intonation) and allows incremental parsing with the competence grammar (Steedman, 2000). Here, we argue 326

We show that CCG augmented with this rule improves CCG's empirical coverage by allowing better analyses of modal verbs in English and causatives in Spanish, and certain coordinate constructions. The D rules are well-behaved; we show this by deriving them both from unary composition and from the logic defined by Baldridge (2002). Both perspectives on D ensure that the new rules are compatible with normal form constraints (Eisner, 1996) for controlling spurious ambiguity. The logic also ensures that the new rules are subject to modalities consistent with those defined by Baldridge and Kruijff (2003). Furthermore, we define a logic that produces Eisner's constraints as grammar internal theorems rather than parsing stipulations.

2 Combinatory Categorial Grammar
CCG uses a universal set of syntactic rules based on the B, T, and S combinators of combinatory logic (Curry and Feys, 1958):
(2) B: ((Bf )g )x = f (g x) T: Txf = f x S: ((Sf )g )x = f x(g x)

CCG functors are functions over strings of symbols, so different linearized versions of each of the combinators have to be specified (ignoring S here):

Proceedings of ACL-08: HLT, pages 326­334, Columbus, Ohio, USA, June 2008. c 2008 Association for Computational Linguistics


(3)

FA: B:

(>) x/ y (<) y (>B ) (<B ) x/ y y\ z

y

x y/ z  x/ z

x\ y  x x\ y  x\ z y\×z  x\×z x\×y  x/ z × (7)

(>B× ) x/ y × (<B× ) y/ z × T: (>T) (<T)

ii. Stan, Max ( (s\np)/np)\(((s\np)/np)/np) iii. a beer, a coke (s\np)\((s\np)/np) iv. and (x\ x)/ x v. gave ((s\np)/np)/np i. vp ii. tv iii. dtv Stan tv\dt a beer vp\tv
<B

x  t/ (t\i x) i x  t\i (t/ x) i (8)

= = = and (x\ x)/ x

s\np (s\np)/np ((s\np)/np)/np Max tv\dt a coke vp\tv
<B > <

The symbols { , , ×, ·} are modalities that allow subtypes of slashes to be defined; this in turn allows the slashes on categories to be defined in a way that allows them to be used (or not) with specific subsets of the above rules. The rules of this multimodal version of CCG (Baldridge, 2002; Baldridge and Kruijff, 2003) are derived as theorems of a Categorial Type Logic (CTL, Moortgat (1997)). This treats CCG as a compilation of CTL proofs, providing a principled, grammar-internal basis for restrictions on the CCG rules, transferring languageparticular restrictions on rule application to the lexicon, and allowing the CCG rules to be viewed as grammatical universals (Baldridge and Kruijff, 2003; Steedman and Baldridge, To Appear). These rules--especially the B rules--allow derivations to be partially associative: given appropriate type assignments, a string ABC can be analyzed as either A(BC) or (AB)C. This associativity leads to elegant analyses of phenomena that demand more effort in less flexible frameworks. One of the best known is "odd constituent" coordination:
(4) (5) Bob gave Stan a beer and Max a coke. I will buy and you will eat a cheeseburger.

vp\dt

vp\dt (vp\dt)\(vp\dt) vp\dt

(9)

Bill s/vp

gave dt

Stan a beer and Max a coke vp\dt vp s
< >

Similarly, I will buy is derived with category s/np by assuming the category (6i) for I and composing that with both verbs in turn. CCG's approach is appealing because such constituents are not odd at all: they simply follow from the fact that CCG is a system of type-based grammatical inference that allows left associativity.

3 Linguistic Motivation for D
CCG is only partially associative. Here, we discuss several situations which require greater associativity and thus cannot be given an adequate analysis with CCG as standardly defined. These structures have in common that a category of the form x|(y|z) must combine with one of the form y|w--exactly the configuration handled by the D schemata in (1). 3.1 Cross-Conjunct Extraction

The coordinated constituents are challenging because they are at odds with standardly assumed phrase structure constituents. In CCG, such constituents simply follow from the associativity added by the B and T rules. For example, given the category assignments in (6) and the abbreviations in (7), (4) is analyzed as in (8) and (9). Each conjunct is a pair of type-raised NPs combined by means of the >B -rule, deriving two composed constituents that are arguments to the conjunction:1
(6)
1

In the first situation, a question word is distributed across auxiliary or subordinating verb categories:
(10) . . . what you can and what you must not base your verdict on.

i. Bob

s/(s\np)

We call this cross-conjunct extraction. It was noted by Pickering and Barry (1993) for English, but to the best of our knowledge it has not been treated in the
have type-raised lexical assignments. We also suppress semantic representations in the derivations for the sake of space.

We follow (Steedman, 2000) in assuming that type-raising applies in the lexicon, and therefore that nominals such as Stan

327


CCG literature, nor noted in other languages. The problem it presents to CCG is clear in (11), which shows the necessary derivation of (10) using standard multimodal category assignments. For the tokens of what to form constituents with you can and you must not, they must must combine directly. The problem is that these constituents (in bold) cannot be created with the standard CCG combinators in (3).
(11) s

3.2

English Auxiliary Verbs

The standard CCG analysis for English auxiliary verbs is the type exemplified in (16) (Steedman, 2000, 68), interpreted as a unary operator over sentence meanings (Gamut, 1991; Kratzer, 1991):
(16) can (s\np)/(s\np) : P et x.P (x)

However, this type is empirically underdetermined, given a widely-noted set of generalizations suggesting that auxiliaries and raising verbs take no subject argument at all (Jacobson, 1990, a.o.).
(17) i. Lack of syntactic restrictions on the subject; ii. Lack of semantic restrictions on the subject; iii. Inheritance of selectional restrictions from the subordinate predicate.

s/(vp/np)

vp/np base your verdict on

s/(vp/np) (s/(vp/np))\(s/(vp/np)) s/(s/np) s/vp (x\ x)/ x s/(vp/np) what you can and s/(s/np) s/vp what you must not

Two arguments are made for (16). First, it is necessary so that type-raised subjects can compose with the auxiliary in extraction contexts, as in (18):
(18) what I can vp/vp
>B >B >

The category for and is marked for non-associativity with , and thus combines with other expressions only by function application (Baldridge, 2002). This ensures that each conjunct is a discrete constituent. Cross-conjunct extraction occurs in other languages as well, including Dutch (12), German (13), Romanian (14), and Spanish (15):
(12) dat ik haar wil en dat ik haar moet helpen. that I her want and that I her can help ". . . that I want to and that I can help her." (13) Wen kann ich und wen darf ich noch wählen? who can I and who may I still choose "Whom can I and whom may I still chose?" (14) Gandeste-te cui çe vrei, consider.imper.2s-refl.2s who.dat what want.2s si cui ¸ çe po¸i, sa dai. t  and who.dat what can.2s to give.subj.2s "Consider to whom you want and to whom you are able to give what." (15) Me lo puedes y me lo debes explicar me it can.2s and me it must.2s ask "You can and should explain it to me."

eat tv

s/(s/np) s/vp

s/vp s

s/np

Second, it is claimed to be necessary in order to account for subject-verb agreement, on the assumption that agreement features are domain restrictions on functors of type s\np (Steedman, 1992, 1996). The first argument is the topic of this paper, and, as we show below, is refuted by the use of the Dcombinator. The second argument is undermined by examples like (19):
(19) There appear to have been [ neither [ any catastrophic consequences ], nor [ a drastic change in the average age of retirement ] ] .

It is thus a general phenomenon, not just a quirk of English. While it could be handled with extra categories, such as (s/(vp/np))/(s/np) for what, this is exactly the sort of strong-arm tactic that inclusion of the standard B, T, and S rules is meant to avoid. 328

In (19), appear agrees with two negative-polaritysensitive NPs trapped inside a neither-nor coordinate structure in which they are licensed. Appear therefore does not combine with them directly, showing that the agreement relation need not be mediated by direct application of a subject argument. We conclude, therefore, that the assignment of the vp/vp type to English auxiliaries and modal verbs is unsupported on both formal and linguistic grounds. Following Jacobson (1990), a more empiricallymotivated assignment is (20):


(20) can

s/s : pt .p

Combining (20) with a type-raised subject presents another instance of the structure in (1), where that question words are represented as variable-binding operators (Groenendijk and Stokhof, 1997):
(21) what I s/vp : P et .P i 
s

This shows another instance of the schema in (1), which is undefined for any of the combinators in (3):
(25) le hicieron (s\np)/s >B   barrer la verada (s|np) (s\np)/((s\np)/np) 

can /s : pt .p >B  

3.4

Analyses Based on D

s/(s/np) : Qet ?y Qy

The preceding data motivates adding D rules (we return to the distribution of the modalities below):
(26) >D >D× >D
×

3.3 The Spanish Causative Construction The schema in (1) is also found in the widelystudied Romance causative construction (Andrews and Manning, 1999, a.m.o), illustrated in (22):
(22) Nos hizo leer El Señor de los Anillos. cl.1p made.3s read the Lord of the Rings "He made us read The Lord of the Rings."

x/ (y/ z) x/ (y\×z)
× x/ ( y \ z)

y/ w y/w · y\·w

 x/ (w/ z)  x/ (w\×z)  x\×(w\ z)  x\ (w\ z)  x\ (w/ z) ×  x/ (w/ z) ×

x/ (y/ z) y\×w  x\×(w/ z) × × ×

>D× (27) <D <D× <D
×

y\ w y/ w × y\·w
· y/w

x \ ( y \ z) x \ ( y / z) × x\×(y/ z)

x\×(y\×z)  x/ (w\×z) ×

The aspect of the construction that is relevant here is that the causative verb hacer appears to take an object argument understood as the subject or agent of the subordinate verb (the causee ). However, it has been argued that Spanish causative verbs do not in fact take objects (Ackerman and Moore, 1999, and refs therein). There are two arguments for this. First, syntactic alternations that apply to objecttaking verbs, such as passivization and periphrasis with subjunctive complements, do not apply to hacer (Luján, 1980). Second, hacer specifies neither the case form of the causee, nor any semantic entailments with respect to it. These are instead determined by syntactic, semantic, and pragmatic factors, such as transitivity, word order, animacy, gender, social prestige, and referential specificity (Finnemann, 1982, a.o). Thus, there is neither syntactic nor semantic evidence that hacer takes an object argument. On this basis, we assign hacer the category (23):
(23) hacer (s\np)/s : P x.cause P x

<D×

To illustrate with example (10), one application of >D allows you and can to combine when the auxiliary is given the principled type assignment s/s, and another combines what with the result.
(28) what you can s/ s · >D ×
>D

s/ (s/ np) s/ (s\×np)

s/ (s\×np) s/ ((s\×np)/ np)

The derivation then proceeds in the usual way. Likewise, D handles the Spanish causative constructions (29) straightforwardly :
(29) lo (s\np)/ ((s\np)/ np) (s\np)/ (s/ np) s\np hice (s\np)/ s
>D >

dormir s/np

However, Spanish has examples of cross-conjunct extraction in which hacer hosts clitics:
(24) No solo le ordenaron, sino que not only cl.dat.3ms ordered.3p but le hicieron barrer la verada. cl.dat.3ms made.3p sweep the sidewalk "They not only ordered him to, but also made him sweep the sidewalk."

The D-rules thus provide straightforward analyses of such constructions by delivering flexible constituency while maintaining CCG's committment to low categorial ambiguity and semantic transparency.

4 Deriving Eisner Normal Form
Adding new rules can have implications for parsing efficiency. In this section, we show that the D rules fit naturally within standard normal form constraints for CCG parsing (Eisner, 1996), by providing both

329


combinatory and logical bases for D. This additionally allows Eisner's normal form constraints to be derived as grammar internal theorems. 4.1 The Spurious Ambiguity Problem CCG's flexibility is useful for linguistic analyses, but leads to spurious ambiguity (Wittenburg, 1987) due to the associativity introduced by the B and T rules. This can incur a high computational cost which parsers must deal with. Several techniques have been proposed for the problem (Wittenburg, 1987; Karttunen, 1989; Hepple and Morrill, 1989; Eisner, 1996). The most commonly used are Karttunnen's chart subsumption check (White and Baldridge, 2003; Hockenmaier and Steedman, 2002) and Eisner's normal-form constraints (Bozsahin, 1998; Clark and Curran, 2007). Eisner's normal form, referred to here as Eisner NF and paraphrased in (30), has the advantage of not requiring comparisons of logical forms: it functions purely on the syntactic types being combined.
(30) For a set S of semantically equivalent2 parse trees for a string ABC, admit the unique parse tree such that at least one of (i) or (ii) holds: i. C is not the argument of (AB) resulting from application of >B 1 + . ii. A is not the argument of (BC) resulting from application of <B 1 + .

Eisner uses a generalized form Bn (n0) of composition that subsumes function application:4
(33) >B n : x/y (34) <B n : y$n y$n x\y   x$n x$n

Based on these theorems, Eisner defines NF as follows (for R, S , T as Bn or S, and Q=Bn 1 ):
(35) Given a parse tree : i. If  is a lexical item, then  is in Eisner-NF. ii. If  is a parse tree R,  ,  and N F ( ), N F ( ), then N F (). iii. If  is not in Eisner-NF, then N F ( ) = Q,  1 ,  2 , and N F () = S,  1 , N F ( T,  2 ,  ) .

As a parsing constraint, (30) is a filter on the set of parses produced for a given string. It preserves all the unique semantic forms generated for the string while eliminating all spurious ambiguities: it is both safe and complete. Given the utility of Eisner NF for practical CCG parsing, the D rules we propose should be compatible with (30). This requires that the generalizations underlying (30) apply to D as well. In the remainder of this section, we show this in two ways. 4.2 Deriving D from B

The implication is that outputs of B1+ rules are inert, using the terminology of Baldridge (2002). Inert slashes are Baldridge's (2002) encoding in OpenCCG3 of his CTL interpretation of Steedman's (2000) ant ecedent-government feature. Eisner derives (30) from two theorems about the set of semantically equivalent parses that a CCG parser will generate for a given string (see (Eisner, 1996) for proofs and discussion of the theorems):
(31) Theorem 1 : For every parse tree , there is a semantically equivalent parse-tree N F () in which no node resulting from application of B or S functions as the primary functor in a rule application. (32) Theorem 2 : If N F () and N F ( ) are distinct parse trees, then their model-theoretic interpretations are distinct.
Two parse trees are semantically equivalent if: (i) their leaf nodes have equivalent interpretations, and (ii) equivalent scope relations hold between their respective leaf-node meanings. 3 http://openccg.sourceforge.net
2

The first is to derive the binary B rules from a unary ^ rule based on the unary combinator B:5
(36) x/y : f xy  (x/z)/(y/z) : hzy xz .f (hx)

^ We then derive D from B and show that clause (iii) of (35) holds of Q schematized over both B and D. Applying D to an argument sequence is equivalent to compound application of binary B:
(37) (((Df )g )h)x = (f g )(hx) (38) ((((BB)f )g )h)x = ((B(f g ))h)x = (f g )(hx)

Syntactically, binary B is equivalent to application ^ of unary B to the primary functor , followed by ^ applying the secondary functor  to the output of B by means of function application (Jacobson, 1999):
We use Steedman's (Steedman, 1996) "$"-convention for representing argument stacks of length n, for n  0. 5 This is Lambek's (1958) Division rule, also known as the "Geach rule" (Jacobson, 1999).
4

330


(39)

 x/y (x/z)/(y/z) x/ z
^ >B

 y/z
>

(45)

 x/(y/z)
^ >B

 y /w (y/! z)/(w/! z)
> ^ >B

(x/! (w/z))/((y/z)/! (w/z)) x/! (w/z)

^ Bn (n  1) is derived by applying B to the primary 2 is derived by 2 functor n times. For example, B ^ applications of B to the primary functor:
(40)  x/ y (x/w)/(y/w)
^ B ^ B

 (y/w)/z

The binary substitution (S) combinator can be similarly incorporated into the system. Unary sub^ ^ stitution S is like B except that it introduces a slash on only the argument-side of the input functor. We ^ stipulate that S returns a category with inert slashes:
(46) ^ (S) (x/y)/z  (x/! z)/(y/! z)

((x/w)/z)/((y/w)/z) (x/w)/z
>

^ The rules for D correspond to application of B to both the primary and secondary functors, followed by function application:
(41)  x/(y/z) (x/(w/z))/((y/z)/(w/z)) x/(w/z)
^ >B

T is by definition unary. It follows that all the binary rules in CCG (including the D-rules) can be reduced to (iterated) instantiations of the unary combinators ^^ B, S, or T plus function application. This provides a basis for CCG in which all com^^ binatory rules are derived from unary B S, and T. 4.3 A Logical Basis for Eisner Normal Form

 y/w (y/z)/(w/z)
> ^ >B

As with Bn , Dn 1 can be derived by iterative appli^ cation of B to both primary and secondary functors. ^ Because B can be derived from B, clause (iii) of (35) is equivalent to the following:
(42) If  is not in Eisner-NF, then N F ( ) = F A, B,  1 ,  2 , such that ^ N F () = S,  1 , N F ( T,  2 ,  )

^ Interpreted in terms of B, both B and D involve ap^ plication of B to the primary functor. It follows that Theorem I applies directly to D simply by virtue of ^ the equivalence between binary B and unary-B+FA. Eisner's NF constraints can then be reinterpreted ^ as a constraint on B requiring its output to be an inert ^ result category. We represent this in terms of the Brules introducing an inert slash, indicated with "!" (adopting the convention from OpenCCG):
(43) x/y : f xy  (x/ z)/(y/ z) : hzy xz f hx
! !

The previous section shows that deriving CCG rules from unary combinators allows us to derive the Drules while preserving Eisner NF. In this section, we present an alternate formulation of Eisner NF with Baldridge's (2002) CTL basis for CCG. This formulation allows us to derive the D-rules as before, and does so in a way that seamlessly integrates with Baldridge's system of modalized functors. In CTL, B and B× are proofs derived via structural rules that allow associativity and permutation of symbols within a sequent, in combination with the slash introduction and elimination rules of the base logic. To control application of these rules, Baldridge keys them to binary modal operators (for associativity) and × (for permutation). Given these, >B is proven in (47):
(47)  x/ y  y/ z [a (  (  (( 
( ) ai )

z]
[/ E ]

y

 

ai )) ai )

[/ E ]

x

[R A ]

x
[/ I ]

Hence, both binary B and D return inert functors:
(44)  x/y (x/! z)/(y/ z) x/! z
> ^ >B !

( 

)

x/ z

 y/z

In a CCG ruleset compiled from such logics, a category must have an appropriately decorated slash in order to be the input to a rule. This means that rules apply universally, without language-specific 331


restrictions. Instead, restrictions can only be declared via modalities marked on lexical categories. ^ Unary B and the D rules in 4.2 can be derived us^ ing the same logic. For example, >B can be derived as in (48):
(48)  x/ y [f y/ z]1 (f 1  (  (( 
(f 1 f1 )

[a
a2 )

z]2
[/E ]

reflecting the intuition that non-lexical arguments have to be "bound" by a superordinate functor. This is based on an interpretation of antecedentgovernment as a unary modality ant that allows structures marked by it to permute to the left or right periphery of a structure:6
(52) ((a × ant b ) × c ) ((a × c ) × ant b ) (a × (ant b × c )) (ant b × (a × c )) x x x x [ALP] [ARP]

y x x
[/ I ] [/ I ] [/ E ] [R A ]

 

a2 )) a2 )

(  

f1 )

x/ z

(x/ z)/ (y/ z)

The D rules are also theorems of this system. For example, the proof for >D applies (48) as a lemma to each of the primary and secondary functors:
(49)   x/ (y/ z)   y/ w
^ >B (x/ (w/ z))/ ((y/ z)/ (w/ z)) ^ >B (y/ z)/ (w/ z) [/E ]

Unlike permutation rules without ant , these permutation rules can only be used in a proof when preceeded by a hypothetical category marked with the 2nt modality. The elimination rule for 2 a modalities introduces a corresponding -marked object in the resulting structure, feeding the rule:
(53) [a 2nt z]1 a z ant a1  x/ y ×
[2 E ]



( 

)

x/ (w/ z)

(ant a1 × )

y\×z [\ E ] × y x
[/ E ] ×

^ >D × involves an associative version of B applied to the primary functor (50), and a permutative version to the secondary functor (51).
(50)  x/ (y\×z) [f (y\×z)/(w\×z)] [g · (f 1 · g 2 ) (  ((  (   (51)  y/w ·
(f 1 f1 ) f1 ) 1

( × (ant a1 × )) [a ant 2nt z]2 a (ant a1 × ( × )) (a × ( × )) ( × ) x

[ALP ]

x
[E ] [\ I ]2 ×

w\×z]

2

y\×z x x

[/E ] · [/ E ] [R A ]

x\×ant 2nt z a

. g 2 )) . g 2 )

x/(w\×z) ·

[/I ] · [/ I ]

(x/(w\×z))/ ((y\×z)/(w\×z)) · · [a z]1 [f w\×z]2
[\ E ] ×

(a1 × f 2 ) ( · (a1 × f 2 )) (a1 × ( · f 2 )) ( · f 2 )  y\×z

w

y y

[/E ] · [LP ] [\ I ] × [/ I ] ·

(y\×z)/(w\×z) ·

Rules for D with appropriate modalities can therefore be incorporated seamlessly into CCG. In the preceding subsection, we encoded Eisner NF with inert slashes. In Baldridge's CTL basis for CCG, inert slashes are represented as functors seeking non-lexical arguments, represented as categories marked with an antecedent-governed feature, 332

Re-introduction of the [a ant 2nt z]k hypothesis a results in a functor the argument of which is marked with ant 2nt . Because lexical categories are not a marked as such, the functor cannot take a lexical argument, and so is effectively an inert functor. In Baldridge's (2002) system, only proofs involving the ARP and ALP rules produce inert categories. In Eisner NF, all instances of B-rules result in inert categories. This can be reproduced in Baldridge's system simply by keying all structural rules to the ant -modality, the result being that all proofs involving structural rules result in inert functors. As desired, the D-rules result in inert categories as well. For example, >D is derived as follows (2nt a and ant are abbreviated as 2 and ):
Note that the diamond operator used here is a syntactic operator, rather than a semantic operator as used in (16) above. The unary modalities used in CTL describe accessibility relationships between subtypes and supertypes of particular categories: in effect, they define feature hierarchies. See Moortgat (1997) and Oehrle (To Appear) for further explanation.
6


(54)



y/ w

[a

2 (w/ z)]1 a w/ z (a 

[b

2 z]2 b w
[2 E ]

[2 E ]

z

b)

[/ E ] [/ E ] [RA]

(  [c 2 z]3 ((  (  (55)  (( 
a) a)

(a a)

 

b)) b)

y y

[E ]2



c)

y
[/ I ]3

y/ 2 z

x/ (y/ 2 z) ( 
( ) d)

(54) . . . (  a) y/ 2 z  
a)) a)

x x

[/ E ] [RA]

Wittenburg (1987) originally proposed using rules based on D as a way to reduce spurious ambiguity, which he achieved by eliminating B rules entirely and replacing them with variations on D. Wittenburg notes that doing so produces as many instances of D as there are rules in the standard rule set. Our proposal retains B and S, but, thanks to Eisner NF, eliminates spurious ambiguity, a result that Wittenburg was not able to realize at the time. Our approach can be incorporated into Eisner NF straightforwardly However, Eisner NF disprefers incremental analyses by forcing right-corner analyses of long-distance dependencies, such as in (58):
(58) (What (does (Grommet (think (Tottie (said (Victor (knows (Wallace ate)))))))))?

[d

2 (w/ z)]4

(( 
)

[E ]1

((  ( 
)



x
[/ I ]4

x/ 2 (w/ z)


(54)-(55) can be used as a lemma corresponding to the CCG rule in (57):
(56)  x/ (y/ 2 z) ( 
)



y/ w
[D]

x/ 2 (w/ z) y/ w 

(57) x/ (y/ ! z)

x/ ! ( w / z)

This means that all CCG rules compiled from the logic--which requires ant to licence the structural rules necessary to prove the rules--return inert functors. Eisner NF thus falls out of the logic because all instances of B, D, and S produce inert categories. This in turns allows us to view Eisner NF as part of a theory of grammatical competence, in addition to being a useful technique for constraining parsing.

For applications that call for increased incrementality (e.g., aligning visual and spoken input incrementally (Kruijff et al., 2007)), CCG rules that do not produce inert categories can be derived a CTL basis that does not require ant for associativity and permutation. The D-rules derived from this kind of CTL specification would allow for left-corner analyses of such dependencies with the competence grammar. An extracted element can "wrap around" the words intervening between it and its extraction site. For example, D would allow the following bracketing for the same example (while producing the same logical form):
(59) (((((((((What does) Grommet) think) Tottie) said) Victor) knows) Wallace) ate)?

5

Conclusion

Including the D-combinator rules in the CCG rule set lets us capture several linguistic generalizations that lack satisfactory analyses in standard CCG. Furthermore, CCG augmented with D is compatible with Eisner NF (Eisner, 1996), a standard technique for controlling derivational ambiguity in CCG-parsers, and also with the modalized version of CCG (Baldridge and Kruijff, 2003). A consequence is that both the D rules and the NF constraints can be derived from a grammar-internal perspective. This extends CCG's linguistic applicability without sacrificing efficiency. 333

Finally, the unary combinator basis for CCG provides an interesting additional specification for generating CCG rules. Like the CTL basis, the unary combinator basis can produce a much wider range of possible rules, such as D rules, that may be relevant for linguistic applications. Whichever basis is used, inclusion of the D-rules increases empirical coverage, while at the same time preserving CCG's computational attractiveness.

Acknowledgments
Thanks Mark Steedman for extensive comments and suggestions, and particularly for noting the relation^ ship between the D-rules and unary B. Thanks also to Emmon Bach, Cem Bozsahin, Jason Eisner, Geert-Jan Kruijff and the ACL reviewers.


References
Farrell Ackerman and John Moore. 1999. Syntagmatic and Paradigmatic Dimensions of Causee Encodings. Linguistics and Philosophy, 24:1­44. Avery D. Andrews and Christopher D. Manning. 1999. Complex Predicates and Information Spreading in LFG. CSLI Publications, Palo Alto, California. Jason Baldridge and Geert-Jan Kruijff. 2003. MultiModal Combinatory Categorial Grammar. In Proceedings of EACL 10, pages 211­218. Jason Baldridge, Sudipta Chatterjee, Alexis Palmer, and Ben Wing. 2007. DotCCG and VisCCG: Wiki and Programming Paradigms for Improved Grammar Engineering with OpenCCG. In Proceedings of GEAF 2007. Jason Baldridge. 2002. Lexically Specified Derivational Control in Combinatory Categorial Grammar. Ph.D. thesis, University of Edinburgh. John Beavers. 2004. Type-inheritance Combinatory Categorial Grammar. In Proceedings of COLING-04, Geneva, Switzerland. Robert Borsley and Kersti Börjars, editors. To Appear. Non-Transformational Syntax: A Guide to Current Models. Blackwell. Cem Bozsahin. 1998. Deriving the Predicate-Argument Structure for a Free Word Order Language. In Proceedings of COLING-ACL '98. Stephen Clark and James Curran. 2007. Wide-Coverage Efficient Statistical Parsing with CCG and Log-Linear Models. Computational Linguistics, 33(4). Haskell B. Curry and Robert Feys. 1958. Combinatory Logic, volume 1. North Holland, Amsterdam. Jason Eisner. 1996. Efficient Normal-Form Parsing for Combinatory Categorial Grammars. In Proceedings of the ACL 34. Michael D Finnemann. 1982. Aspects of the Spanish Causative Construction. Ph.D. thesis, University of Minnesota. L. T. F. Gamut. 1991. Logic, Language, and Meaning, volume II. Chicago University Press. Jeroen Groenendijk and Martin Stokhof. 1997. Questions. In Johan van Benthem and Alice ter Meulen, editors, Handbook of Logic and Language, chapter 19, pages 1055­1124. Elsevier Science, Amsterdam. Mark Hepple and Glyn Morrill. 1989. Parsing and Derivational Equivalence. In Proceedings of EACL 4. Julia Hockenmaier and Mark Steedman. 2002. Generative Models for Statistical Parsing with Combinatory Categorial Grammar. In Proceedings. of ACL 40, pages 335­342, Philadelpha, PA. Pauline Jacobson. 1990. Raising as Function Composition. Linguistics and Philosophy, 13:423­475.

Pauline Jacobson. 1999. Towards a Variable-Free Semantics. Linguistics and Philosophy, 22:117­184. Lauri Karttunen. 1989. Radical Lexicalism. In Mark Baltin and Anthony Kroch, editors, Alternative Conceptions of Phrase Structure. University of Chicago Press, Chicago. Angelika Kratzer. 1991. Modality. In Arnim von Stechow and Dieter Wunderlich, editors, Semantics: An International Handbook of Contemporary Semantic Research, pages 639­650. Walter de Gruyter, Berlin. Geert-Jan M. Kruijff, Pierre Lison, Trevor Benjamin, Henrik Jacobsson, and Nick Hawes. 2007. Incremental, Multi-Level Processing for Comprehending Situated Dialogue in Human-Robot Interaction. In Language and Robots: Proceedings from the Symposium (LangRo'2007), Aveiro, Portugal. Joachim Lambek. 1958. The mathematics of sentence structure. American Mathematical Monthly, 65:154­ 169. Marta Luján. 1980. Clitic Promotion and Mood in Spanish Verbal Complements. Linguistics, 18:381­484. Michael Moortgat. 1997. Categorial Type Logics. In Johan van Benthem and Alice ter Meulen, editors, Handbook of Logic and Language, pages 93­177. North Holland, Amsterdam. Richard T Oehrle. To Appear. Multi-Modal Type Logical Grammar. In Boersley and Börjars (Borsley and Börjars, To Appear). Martin Pickering and Guy Barry. 1993. Dependency Categorial Grammar and Coordination. Linguistics, 31:855­902. David Reitter, Julia Hockenmaier, and Frank Keller. 2006. Priming Effects in Combinatory Categorial Grammar. In Proceedings of EMNLP-2006. Mark Steedman and Jason Baldridge. To Appear. Combinatory Categorial Grammar. In Borsley and Börjars (Borsley and Börjars, To Appear). Mark Steedman. 1996. Surface Structure and Interpretation. MIT Press. Mark Steedman. 2000. The Syntactic Process. MIT Press. Michael White and Jason Baldridge. 2003. Adapting Chart Realization to C C G. In Proceedings of ENLG. Michael White. 2006. Efficient Realization of Coordinate Structures in Combinatory Categorial Grammar. Research on Language and Computation, 4(1):39­75. Kent Wittenburg. 1987. Predictive Combinators: A Method for Efficient Processing of Combinatory Categorial Grammars. In Proceedings of ACL 25. Luke Zettlemoyer and Michael Collins. 2007. Online Learning of Relaxed C C G Grammars for Parsing to Logical Form. In Proceedings of EMNLP-CoNLL 2007.

334