k-Valued Non-Associative Lambek Grammars are Learnable from Function-Argument Structures

AbstractThis paper is concerned with learning categorial grammars in the model of Gold. We show that rigid and k-valued non-associative Lambek grammars are learnable from function-argument structured sentences. In fact, function-argument structures are natural syntactical decompositions of sentences in sub-components with the indication of the head of each sub-component.This result is interesting and surprising because for every k, the class of k-valued NL grammars has infinite elasticity and one could think that it is not learnable, which is not true. Moreover, these classes are very close to unlearnable classes like k-valued associative Lambek grammars learned from function-argument sentences or k-valued non-associative Lambek calculus grammars learned from well-bracketed list of words or from strings. Thus, the k-valued non-associative Lambek grammars learned from function-argument sentences is at the frontier between learnable and unlearnable classes of languages