HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Yet Another ${\cal O}(n^6)$ Recognition Algorithm for Mildly Context-Sensitive Languages

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.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 2:11:11 PM
Last modification on : Thursday, February 3, 2022 - 11:18:12 AM
Long-term archiving on: : Thursday, March 24, 2011 - 1:31:55 PM


  • HAL Id : inria-00073964, version 1



Pierre Boullier. Yet Another ${\cal O}(n^6)$ Recognition Algorithm for Mildly Context-Sensitive Languages. [Research Report] RR-2730, INRIA. 1995. ⟨inria-00073964⟩



Record views


Files downloads