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

Proceedings of ACL-08: HLT, pages 326–334, Columbus, Ohio, USA, June 2008. c⃝2008 Association for Computational Linguistics 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 Combina- tory Categorial Grammar (CCG) fails to pro- vide satisfactory analyses for a number of syn- tactic 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. 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 va- riety of tasks, such as wide-coverage parsing (Hock- enmaier 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 engi- neering (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 sup- ports elegant analyses of several phenomena (e.g., coordination, long-distance extraction, and intona- tion) and allows incremental parsing with the com- petence grammar (Steedman, 2000). Here, we argue that even with its flexibility, CCG as standardly de- fined 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.ghx) We show that CCG augmented with this rule im- proves 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 com- patible 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 Krui- jff (2003). Furthermore, we define a logic that pro- duces Eisner’s constraints as grammar internal theo- rems 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(gx) T: Txf = fx S: ((Sf)g)x = fx(gx) CCG functors are functions over strings of symbols, so different linearized versions of each of the com- binators have to be specified …

Content truncated to 500 words