Conjunctive Grammars

This paper introduces a class of formal grammars made up by augmenting the formalism of context-free grammars with an explicit set-theoretic intersection operation. It is shown that conjunctive grammars can generate some important non-contextfree language constructs, including those not in the intersection closure of context-free languages, and that they can provide very succinct descriptions of some context-free languages and finite intersections of context-free languages. On the other hand, it is proved that conjunctive grammars can still be parsed in cubic time and that the notion of the derivation tree is retained, which gives reasonable hope for their practical applicability.