Range Concatenation Grammars

Pierre Boullier


Abstract
In this paper we present Range Concatenation Grammars, a syntactic formalism which possesses many attractive features among which we underline here, power and closure properties. For example, Range Concatenation Grammars are more powerful than Linear Context-Free Rewriting Systems though this power is not reached to the detriment of efficiency since its sentences can always be parsed in polynomial time. Range Concatenation Languages are closed both under intersection and complementation and these closure properties may allow to consider novel ways to describe some linguistic processings. We also present a parsing algorithm which is the basis of our current prototype implementation.
Anthology ID:
2000.iwpt-1.8
Volume:
Proceedings of the Sixth International Workshop on Parsing Technologies
Month:
February 23-25
Year:
2000
Address:
Trento, Italy
Editors:
Alberto Lavelli, John Carroll, Robert C. Berwick, Harry C. Bunt, Bob Carpenter, John Carroll, Ken Church, Mark Johnson, Aravind Joshi, Ronald Kaplan, Martin Kay, Bernard Lang, Alon Lavie, Anton Nijholt, Christer Samuelsson, Mark Steedman, Oliviero Stock, Hozumi Tanaka, Masaru Tomita, Hans Uszkoreit, K. Vijay-Shanker, David Weir, Mats Wiren
Venue:
IWPT
SIG:
SIGPARSE
Publisher:
Association for Computational Linguistics
Note:
Pages:
53–64
Language:
URL:
https://aclanthology.org/2000.iwpt-1.8
DOI:
Bibkey:
Cite (ACL):
Pierre Boullier. 2000. Range Concatenation Grammars. In Proceedings of the Sixth International Workshop on Parsing Technologies, pages 53–64, Trento, Italy. Association for Computational Linguistics.
Cite (Informal):
Range Concatenation Grammars (Boullier, IWPT 2000)
Copy Citation:
PDF:
https://aclanthology.org/2000.iwpt-1.8.pdf