Extensions of context-free grammars and categorial grammars

We shall consider two formal systems invented for formalizing natural language grammar. The first one, context-free grammars, is due to N. Chomsky, the second one, categorial grammars, emerged in the works of K. Ajdukiewicz and J. Lambek. These two formalisms generate the same class of formal languages [M. Pentus 1992], and this class appears to be insufficient for describing nontrivial linguistic phenomena. In this talk we survey several approaches of extending these formalisms preserving there good properties, in particular algorithmic ones.