Parsing Mildly Context-sensitive RMS

Tilman Becker, Dominik Heckmann


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:
Bibkey:
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)
Copy Citation:
PDF:
https://aclanthology.org/2000.iwpt-1.29.pdf