Abstract:
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.
