Efficient Parsing for CCGs with Generalized Type-Raised Categories (IRCS
Technical Report 97-16)

Nobo Komagata

A type of `non-traditional constituents' motivates an extended class of
Combinatory Categorial Grammars, CCGs with Generalized Type-Raised
Categories (CCG-GTRC) involving variables. Although the class of standard
CCGs is known to be polynomially parsable, use of variables suggests more
processing for GTRCs. This paper argues that polynomial parsing is still
possible for CCG-GTRC from practical and theoretical points of view. First,
we show that an experimental parser runs polynomially in practice on a
realistic fragment of Japanese by eliminating spurious ambiguity and
excluding genuine ambiguities. Then, we present a worst-case polynomial
recognition algorithm for CCG-GTRC by extending the polynomial algorithm for
the standard CCGs.