A polynomial algorithm for the membership problem with categorial grammars

AbstractThis article presents an overview of a framework called categorial grammars from a theoretical and algorithmic perspective. It provides an introduction to the formalisms of these grammars and of the tools they use (the Lambek Calculus) for theoretical computer scientists who are not familiar with them. We give a clear presentation of the main classical and recent results on these grammars, especially those concerning their links with context-free grammars.The purpose is also to use these results so as to efficiently solve the membership problem with categorial grammars. We compare the complexity of the algorithms for this problem deduced from the initial formulation of the categorial grammars and the one obtained by translating these grammars into context-free formalism and by applying the Cocke-Kasami-Younger algorithm. We show that a polynomial algorithm is always available