tailieunhanh - Báo cáo khoa học: "k-valued Non-Associative Lambek Categorial Grammars are not Learnable from Strings"

This paper is concerned with learning categorial grammars in Gold’s model. In contrast to k-valued classical categorial grammars, k-valued Lambek grammars are not learnable from strings. This result was shown for several variants but the question was left open for the weakest one, the non-associative variant NL. We show that the class of rigid and kvalued NL grammars is unlearnable from strings, for each k; this result is obtained by a specific construction of a limit point in the considered class, that does not use product operator. . | k-valued Non-Associative Lambek Categorial Grammars are not Learnable from Strings Denis Bechet INRIA IRISA Campus Universitaire de Beaulieu Avenue du General Leclerc 35042 Rennes Cedex France Annie Foret Universite de Rennesl IRISA Campus Universitaire de Beaulieu Avenue du General Leclerc 35042 Rennes Cedex France Abstract This paper is concerned with learning categorial grammars in Gold s model. In contrast to . -valued classical categorial grammars -valued Lambek grammars are not learnable from strings. This result was shown for several variants but the question was left open for the weakest one the non-associative variant NL. We show that the class of rigid and -valued NL grammars is unlearnable from strings for each this result is obtained by a specific construction of a limit point in the considered class that does not use product operator. Another interest of our construction is that it provides limit points for the whole hierarchy of Lambek grammars including the recent pregroup grammars. Such a result aims at clarifying the possible directions for future learning algorithms it expresses the difficulty of learning categorial grammars from strings and the need for an adequate structure on examples. 1 Introduction Categorial grammars Bar-Hillel 1953 and Lam-bek grammars Lambek 1958 Lambek 1961 have been studied in the field of natural language processing. They are well adapted to learning perspectives since they are completely lexicalized and an actual way of research is to determine the sub-classes of such grammars that remain learnable in the sense of Gold Gold 1967 . We recall that learning here consists to define an algorithm on a finite set of sentences that converge to obtain a grammar in the class that generates the examples. Let G be a class of grammars that we wish to learn from positive examples. Formally let L G denote the language associated with grammar G and let V be a given alphabet a learning .