Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo khoa học: "Rigid Grammars in the Associative-Commutative Lambek Calculus are not Learnable"

In (Kanazawa, 1998) it was shown that rigid Classical Categorial Grammars are learnable (in the sense of (Gold, 1967)) from strings. Surprisingly 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 Lambek calculus) and LP0 (same, but allowing the empty sequent in derivations) will be shown. | Rigid Grammars in the Associative-Commutative Lambek Calculus are not Learnable Christophe Costa Florencio UiL OTS Faculty of Arts Utrecht University costa@let.uu.nl Abstract In Kanazawa 1998 it was shown that rigid Classical Categorial Grammars are learnable in the sense of Gold 1967 from strings. Surprisingly there are recent negative results for among others rigid associative Lambek L grammars. In this paper the non-lcarnability of the class of rigid grammars in LP Associative-Commutative Lam-bek calculus and LPg same but allowing the empty sequent in derivations will be shown. 1 Introduction The question of learnability of catcgorial grammar 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 Categorial 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 identification in the limit from positive data as introduced in Gold 1967 .1 In order to show the non-learnability of rigid LP and LPj we 1 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 B 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 G L G L is knowm as a naming .