Efficient Parsing for CCGs with Generalized Type-raised Categories

Nobo Komagata


Abstract
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, unrestricted use of variables can destroy this essential requirement for a practical parser. This paper argues for polynomial parsability of 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.
Anthology ID:
1997.iwpt-1.17
Volume:
Proceedings of the Fifth International Workshop on Parsing Technologies
Month:
September 17-20
Year:
1997
Address:
Boston/Cambridge, Massachusetts, USA
Editors:
Anton Nijholt, Robert C. Berwick, Harry C. Bunt, Bob Carpenter, Eva Hajicova, Mark Johnson, Aravind Joshi, Ronald Kaplan, Martin Kay, Bernard Lang, Alon Lavie, Makoto Nagao, Mark Steedman, Masaru Tomita, K. Vijay-Shanker, David Weir, Kent Wittenburg, Mats Wiren
Venue:
IWPT
SIG:
SIGPARSE
Publisher:
Association for Computational Linguistics
Note:
Pages:
135–146
Language:
URL:
https://aclanthology.org/1997.iwpt-1.17
DOI:
Bibkey:
Cite (ACL):
Nobo Komagata. 1997. Efficient Parsing for CCGs with Generalized Type-raised Categories. In Proceedings of the Fifth International Workshop on Parsing Technologies, pages 135–146, Boston/Cambridge, Massachusetts, USA. Association for Computational Linguistics.
Cite (Informal):
Efficient Parsing for CCGs with Generalized Type-raised Categories (Komagata, IWPT 1997)
Copy Citation:
PDF:
https://aclanthology.org/1997.iwpt-1.17.pdf