Generative Power of CCGs with Generalized Type-Raised Categories

Generative Power of CCGs with Generalized Type-Raised Categories Nobo Komagata Department of Computer and Information Science University of Pennsylvania Philadelphia, PA 19104 komaga t a@ 1 inc. c i s. upenn, edu Abstract This paper shows that a class of Combinatory Categorial Grammars (CCGs) augmented with a linguistically-motivated form of type raising involving variables is weakly equivalent to the standard CCGs not involving variables. The proof is based on the idea that any instance of such a grammar can be simulated by a standard CCG. 1 Introduction The class of Combinatory Categorial Grammars (CCG- Std) was proved to be weakly equivalent to Linear Index Grammars and Tree Adjoining Grammars (Joshi, Vijay- Shanker, and Weir, 1991; Vijay-Shanker and Weir, 1994). But CCG-Std cannot handle the generalization of type raising that has been used in accounting for various lin- guistic phenomena including: coordination and extrac- tion (Steedman, 1985; Dowty, 1988; Steedman, 1996), prosody (Prevost and Steedman, 1993), and quantifier scope (Park, 1995). Intuitively, all of these phenomena call for a non-traditional, more flexible notion of consti- tuency capable of representing surface structures inclu- ding "(Subj V) (Obj)" in English. Although lexical type raising involving variables can be introduced to derive such a constituent? unconstrained use of variables can increase the power. For example, a grammar involving (T\z)/(T\v) can generate a language A"B"C"D"E" which CCG-Std cannot (Hoffman, 1993). This paper argues that there is a class of grammars which allows the use of linguistically-motivated form of type raising involving variables while it is still weakly equivalent to CCG-Std. A class of grammars, CCG- GTRC, is introduced in the next section as an extension to CCG-Std. Then we show that CCG-GTRC can actually be simulated by a CCG-Std, proving the equivalence. °Thanks to Mark Steedman, Beryl Hoffman, Anoop Sarkar, and the reviewers. The research was supported in part by NSF Grant Nos. IRI95-04372, STC-SBR-8920230, ARPA Grant No. N66001-94-C6043, and ARID Grant No. DAAH04-94- G0426. IOur lexieal rules to introduce type raising are non-recursive and thus do not suffer from the problem of the overgeneration discussed in (Carpenter, 1991). 2 CCGs with Generalized Type-Raised Categories In languages like Japanese, multiple NPs can easily form a non-traditional constituent as in "[(Subj I Objl) & (Subj2 Obj2)] Verb". The proposed ~ammars (CCG-GTRC) admit lexical type-raised categories (LTRC) of the form "1"/(T\a) or'l'\ (T/a) where T is a variable over categories and a is a constant category (Const). 2 Then, composition of LTRCs can give rise to a class of categories having the formT/(T\a .... \at) or T\ (T/a .... /at), representing a multiple-NP constituent exemplified by "Subjl Objt". We call these categories generalized type-raised cate- gories (GTRC) and each ai of a GTRC an argument (of the GTRC). The introduction of GTRCs affects the use of combi- natory rules: functional application ">: z/y + y ---, z" and generalized functional composition ">B ~ (x) : z/y + ylzt ...[zk --- zlzl ...[z~" where k is bounded by a grammar-dependent kma~ as in CCG-Std. 3 This paper assumes …

Content truncated to 500 words