Yet Another 0(n6) Recognition Algorithm for Mildly Context-Sensitive Languages

Pierre Boullier


Abstract
Vijay-Shanker and Weir have shown in [17] that Tree Adjoining Grammars and Combinatory Categorial Grammars can be transformed into equivalent Linear Indexed Grammars (LIGs) which can be recognized in 0(n6) time using a Cocke-Kasami-Younger style algorithm. This paper exhibits another recognition algorithm for LIGs, with the same upper-bound complexity, but whose average case behaves much better. This algorithm works in two steps: first a general context-free parsing algorithm (using the underlying context-free grammar) builds a shared parse forest, and second, the LIG properties are checked on this forest. This check is based upon the composition of simple relations and does not require any computation of symbol stacks.
Anthology ID:
1995.iwpt-1.7
Volume:
Proceedings of the Fourth International Workshop on Parsing Technologies
Month:
September 20-24
Year:
1995
Address:
Prague and Karlovy Vary, Czech Republic
Editors:
Eva Hajicova, Bernard Lang, Robert Berwick, Harry Bunt, Bob Carpenter, Ken Church, Aravind Joshi, Ronald Kaplan, Martin Kay, Makoto Nagao, Anton Nijholt, Mark Steedman, Henry Thompson, Masaru Tomita, K. Vijay-Shanker, Yorick Wilks, Kent Wittenburg
Venues:
IWPT | WS
SIG:
SIGPARSE
Publisher:
Association for Computational Linguistics
Note:
Pages:
34–47
Language:
URL:
https://aclanthology.org/1995.iwpt-1.7
DOI:
Bibkey:
Cite (ACL):
Pierre Boullier. 1995. Yet Another 0(n6) Recognition Algorithm for Mildly Context-Sensitive Languages. In Proceedings of the Fourth International Workshop on Parsing Technologies, pages 34–47, Prague and Karlovy Vary, Czech Republic. Association for Computational Linguistics.
Cite (Informal):
Yet Another 0(n6) Recognition Algorithm for Mildly Context-Sensitive Languages (Boullier, IWPT-WS 1995)
Copy Citation:
PDF:
https://aclanthology.org/1995.iwpt-1.7.pdf