k-Valued Non-Associative Lambek Categorial Grammars are not Learnable from Strings

k-valued Non-Associative Lambek Categorial Grammars are not Learnable from Strings Denis B´echet INRIA, IRISA Campus Universitaire de Beaulieu Avenue du G´en´eral Leclerc 35042 Rennes Cedex France Denis.Bechet@irisa.fr Annie Foret Universit´e de Rennes1, IRISA Campus Universitaire de Beaulieu Avenue du G´en´eral Leclerc 35042 Rennes Cedex France Annie.Foret@irisa.fr Abstract This paper is concerned with learning cat- egorial grammars in Gold’s model. contrast to k-valued classical categorialIn grammars, k-valued Lambek grammars are not learnable from strings. This re- sult was shown for several variants but the question was left open for the weak- est one, the non-associative variant NL. We show that the class of rigid and k- valued 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. Another interest of our construction is that it provides limit points for the whole hier- archy of Lambek grammars, including the recent pregroup grammars. Such a result aims at clarifying the pos- sible directions for future learning algo- rithms: it expresses the difficulty of learn- ing categorial grammars from strings and the need for an adequate structure on ex- amples. 1 Introduction Categorial grammars (Bar-Hillel, 1953) and Lam- bek grammars (Lambek, 1958; Lambek, 1961) have been studied in the field of natural language process- ing. 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 algorith- m is a function φ from finite sets of words in V ∗ to G, such that for all G ∈ G with L(G) =< ei >i∈N there exists a grammar G′ ∈ G and there exists n0 ∈ N such that: ∀n > n0 φ({e1, . . . , en}) = G′ ∈ G with L(G′) = L(G). After pessimistic unlearnability results in (Gold, 1967), learnability of non trivial classes has been proved in (Angluin, 1980) and (Shinohara, 1990). Recent works from (Kanazawa, 1998) and (Nicolas, 1999) following (Buszkowski and Penn, 1990) have answered the problem for different sub-classes of classical categorial grammars (we recall that the w- hole class of classical categorial grammars is equiv- alent to context free grammars; the same holds for the class of Lambek grammars (Pentus, 1993) that is thus not learnable in Gold’s model). The extension of such results for Lambek gram- mars is an interesting challenge that is addressed by works on logic types from (Dudau-Sofronie et al., 2001) (these grammars enjoy a direct link with Mon- tague semantics), learning …

Content truncated to 500 words