Abstract
We introduce Recursive Matrix Systems (RMS) which encompass mildly context-sensitive formalisms and present efficient parsing algorithms for linear and context-free variants of RMS. The time complexities are đť’Ş(n2h + 1), and đť’Ş(n3h) respectively, where h is the height of the matrix. It is possible to represent Tree Adjoining Grammars (TAG [1], MC-TAG [2], and R-TAG [3]) as RMS uniformly.- Anthology ID:
- 2000.iwpt-1.29
- 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:
- 293–294
- Language:
- URL:
- https://aclanthology.org/2000.iwpt-1.29
- DOI:
- Cite (ACL):
- Tilman Becker and Dominik Heckmann. 2000. Parsing Mildly Context-sensitive RMS. In Proceedings of the Sixth International Workshop on Parsing Technologies, pages 293–294, Trento, Italy. Association for Computational Linguistics.
- Cite (Informal):
- Parsing Mildly Context-sensitive RMS (Becker & Heckmann, IWPT 2000)
- PDF:
- https://preview.aclanthology.org/nschneid-patch-4/2000.iwpt-1.29.pdf