Generative Power of CCGs with Generalized Type-Raised Categories (IRCS
Technical Report 97-15)

Nobo Komagata

A type of `non-traditional constituents' motivates an extended class of
Combinatory Categorial Grammars (CCG), CCGs with Generalized Type-Raised
Categories (CCG-GTRC) involving variables. Although the class of standard
CCGs is proved to be equivalent to Linear Indexed Grammars and Tree
Adjoining Grammars, use of variables can increase the power beyond these
grammars. In order to establish a desired context with respect to
computational complexity, this paper shows that there is a subclass of
CCG-GTRC which is still weekly equivalent to the standard CCGs. The idea
behind the proof is that the behavior of GTRCs can be simulated by
appropriately setting the lexicon of a standard CCG.