Yet Another ${cal O}n^6$ Recognition Algorithm for Mildly Context-Sensitive LanguagesReport as inadecuate




Yet Another ${cal O}n^6$ Recognition Algorithm for Mildly Context-Sensitive Languages - Download this document for free, or read online. Document in PDF available to download.

1 ATOLL - Software tools for natural language Inria Paris-Rocquencourt

Abstract : Vijay-Shanker and Weir have shown in \cite{VSW94} that Tree Adjoining Grammars and Combinatory Categorial Grammars can be transformed into equivalent Linear Indexed Grammars LIGs which can be recognized in ${\cal O}n^6$ 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.

Keywords : PARSE TREE SHARED PARSE FOREST AMBIGUITY CONTEXT-SENSITIVE PARSING





Author: Pierre Boullier -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents