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
- 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/starsem-semeval-split/2000.iwpt-1.29.pdf