RR-3611 : 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.

Résumé : Les grammaires non-contextuelles et l'analyse en temps cubique sont si étroitement associées dans l'esprit des gens qu'ils pensent souvent que toute extension nécessiterait obligatoirement un temps d'analyse supérieur. Bien sûr, c'est une erreur, et ce papier présente une généralisation des grammaires non-contextuelles qui conserve un temps d'analyse cubique. Cette extension, qui définit une sous-classe des langages contextuels, peut présenter un intérêt à la fois théorique et pratique. La classe de langages définie par ces grammaires est close par intersection et complémentation (en fait c'est la classe à laquelle appartiennent les intersections et le complémentaire des langages non-contextuels). D'un autre côté, ces grammaires peuvent être considérées comme étant un formalisme modérément contextuel et, en conséquence, être utilisées en traitement de la langue naturelle.

RR-3611 - A Cubic Time Extension of Context-Free Grammars