From Unification Compactness to Learnability

• Autorzy: Marciniec J.
• Języki publikacji: EN

Abstrakty

EN

In this paper we explain how to derive learnability of some classes of categorial languages as a consequence of the a property that have unifiable infinite sets of types, namely unification compactness. At first we present an alternate (with respect to [6]) proof of learnability of rigid languages, that introduces our method. Then we prove learnability of the class of semi-rigid languages, which lies in between (learnable) class of rigid languages and (not learnable) class of optimal (as defined by Kanazawa in [6]) languages.

Słowa kluczowe

EN

categorial grammars; unification; learnability

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 81, nr 4
• Strony: 473--484
• Opis fizyczny: bibliogr. 10 poz.

Twórcy

autor

Marciniec J.

• Collegium Mathematicum, ul. Umultowska 87, 61-614 Poznań, Poland,

Bibliografia

• [1] van Benthem, J.: Categorial Equations, in: Klein and van Benthem [7].
• [2] Buszkowski,W.: Discovery Procedures for Categorial Grammars, in: Klein and van Benthem [7].
• [3] Buszkowski, W.: Solvable Problems for Classical Categorial Grammars, Bull. Pol. Acad. Scie. Math., (35), 1987, 373-382.
• [4] Buszkowski, W., Penn, G.: Categorial Grammars Determined from Linguistic Data by Unification, Studia Logica, XLIX(4), 1990, 431-454.
• [5] Gold, E. M.: Language Identification in the Limit, Information and Control, 10, 1967, 447-474.
• [6] Kanazawa, M.: Learnable Classes of Categorial Grammars, Studies in Logic, Language and Information, CSLI Publications & FoLLI, Stanford, California, 1998.
• [7] Klein, E., van Benthem, J., Eds.: Categories, Polymorphism and Unification, Universiteit van Amsterdam, Amsterdam, 1987.
• [8] Marciniec, J.: Infinite Set Unification with Application to Categorial Grammar, Studia Logica, LVIII(3), 1997, 339-355.
• [9] Marciniec, J.: Optimal Unification of Infinite Sets of Types, Fundamenta Informaticae, 62(3,4), 2004, 395-407, ISSN 0169-2968.
• [10] Wright, K.: Identification of unions of languages drawn from an identifiable class, COLT '89: Proceedings of the second annual workshop on Computational learning theory, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1989, ISBN 1-55860-086-8.