A Cubic Time Extension of Context-Free Grammars

Abstract : Context-free grammars and cubic time parsing are so related in people's minds that they often think that parsing any extension of context-free grammars must need some extra time. Of course, this is not true and this paper presents a generalization of context-free grammars which keeps a cubic time complexity. This extension, which defines a sub-class of context-sensitive languages, has both a theoretical and a practical interest. The class of languages defined by these grammars is closed under both intersection and complementation (in fact it is the class containing the intersection and the complementation of context-free languages). On the other hand, these grammars can be considered as being mildly context-sensitive and can therefore be used in natural language processing.
Type de document :
Rapport
[Research Report] RR-3611, INRIA. 1999
Liste complète des métadonnées

https://hal.inria.fr/inria-00073067
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 11:44:07
Dernière modification le : vendredi 25 mai 2018 - 12:02:02
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:33:12

Fichiers

Identifiants

  • HAL Id : inria-00073067, version 1

Collections

Citation

Pierre Boullier. A Cubic Time Extension of Context-Free Grammars. [Research Report] RR-3611, INRIA. 1999. 〈inria-00073067〉

Partager

Métriques

Consultations de la notice

96

Téléchargements de fichiers

202