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.
Type de document :
Rapport
[Research Report] RR-2730, INRIA. 1995
Liste complète des métadonnées

https://hal.inria.fr/inria-00073964
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 14:11:11
Dernière modification le : vendredi 25 mai 2018 - 12:02:02
Document(s) archivé(s) le : jeudi 24 mars 2011 - 13:31:55

Fichiers

Identifiants

  • HAL Id : inria-00073964, version 1

Collections

Citation

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

Partager

Métriques

Consultations de la notice

97

Téléchargements de fichiers

89