Rigid grammars in the Associative-Commutative Lambek Calculus are not learnable

Rigid Grammars in the Associative-Commutative Lambek Calculus are not Learnable Christophe Costa Florencio UiL OTS, Faculty of Arts Utrecht University costa@let.uu.n1 Abstract In (Kanazawa, 1998) it was shown that rigid Classical Categorial Gram- mars are learnable (in the sense of (Gold, 1967)) from strings. Surpris- ingly there are recent negative results for, among others, rigid associative Lamb ek (L) grammars. In this paper the non-lcarnability of the class of rigid grammars in LP (Associative-Commutative Lam- bek calculus) and LP0 (same, but al- lowing the empty sequent in deriva- tions) will be shown. 1 Introduction The question of learnability of categorial gram- mar (CG) was first taken up in (Kanazawa, 1998). Categorial grammar is an example of a radically lexicalized formalism, the details of which will be discussed in Section 2. Kanazawa studied only subclasses of Classical Catego- rial Grammar, results for subclasses of Lam- bek grammars can be found in (Foret and Nir, 2002a), (Foret and Nir, 2002b). The model of learnability used here is iden- tification in the limit from positive data as in- troduced in (Gold, 1967). 1 In order to show the non-learnability of rigid LP and LP0 we 'Space restrictions do not allow a full exposition of this model. The interested reader is referred to the first two chapters of (Kanazawa, 1998). construct so-called limit points (to be defined in Section 3) for these classes. 2 The Lambek Calculus Categorial grammar originated in (Aj- dukiewicz, 1935) and was further developed in (Bar-Hillel, 1953) and (Lambek, 1958). This paper will only give a brief introduction in this field, (Casadio, 1988) or (Moortgat, 1997) offers a more comprehensive overview. A categorial grammar is a set of assignments of types to symbols from a fixed alphabet E, the types are either primitives or are composed from types with the binary connectives /, \ , Rules specify how types are to be combined to form new types. A string is said to be in the language generated by grammar G (written as s e L(C), L is known as a naming function) if G assigns types to the symbols in the string such that these types can be combined to de- rive the distinguished type, normally written as s or t. Definition 1 A domain subtype is a subtype that is in domain position, i.e. for the type ((Al B)IC) the domain subtypes are B and C. For the type (CVB\A)) the domain subtypes are C and B. A range subtype is a subtype that is in range position, i.e. for the type ((AI B)IC) the range subtypes are (Al B) and A. For the type (CVB\A)) the range subtypes are (B\A) and A. 2 2Note that product is ignored in this definition. 75 (F. B) I- A� I' H Al B� �Al- B [I Ei [11-] � AIB�(T, A) H A (B, 1') I- A F H B� �A H B A [\E] r B \ A� (F; A) h A [H A A I- B (F,A)H A. B …

Content truncated to 500 words