Rough Sets and Learning by Unification

• Autorzy: Buszkowski W.
• Języki publikacji: EN

Abstrakty

EN

We apply basic notions of the theory of rough sets, due to Pawlak], to explicate certain properties of unification-based learning algorithms for categorial grammars, introduced in and further developed in e.g]. The outcomes of these algorithms can be used to compute both the lower and the upper approximation of the searched language with respect to the given, finite sample. We show that these methods are also appropriate for other kinds of formal grammars, e.g. context-free grammars and context-sensitive grammars.

Słowa kluczowe

EN

rough sets; learning grammars

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 75, nr 1-4
• Strony: 107--121
• Opis fizyczny: bibliogr. 35 poz.

Twórcy

autor

Buszkowski W.

• Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Umultowska 87, 61-614 Poznań, Poland,

Bibliografia

• [1] Ajdukiewicz, K.: Die syntaktische Konnexität, Studia Philosophica, 1, 1935, 1.
• [2] Bar-Hillel, Y., Gaifman, C., Shamir, E.: On categorial and phrase structure grammars, Bulletin Res Council Israel, F(9), 1960, 155-166.
• [3] Bechet, D., Foret, A.: k-valued non-associative Lambek grammars are learnable from generalized functorargument structures, Theoretical Computer Science, 355(2), 2006, 139-152.
• [4] van Benthem, J.: Language in Action. Categories, Lambdas and Dynamic Logic, Studies in Logic and The Foundations of Mathematics, North-Holland, Amsterdam, 1991.
• [5] van Benthem, J., ter Meulen, A., Eds.: Handbook of Logic and Language, Elsevier Science B. V., 1997.
• [6] Buszkowski, W.: Discovery Procedures for Categorial Grammars, in: Categories, Polymorphism and Unification (E. Klein, J. van Benthem, Eds.), Universiteit van Amsterdam, Amsterdam, 1987, 36-64.
• [7] Buszkowski, W.: Generative Power of Categorial Grammars, in: Categorial Grammars and Natural Language Structures (R. T. Oehrle, E. Bach, D. Wheeler, Eds.), D. Reidel, Dordrecht, 1988, 69-94.
• [8] Buszkowski,W.: Mathematical Linguistics and Proof Theory, in: van Benthem and terMeulen [5], 683-736.
• [9] Buszkowski, W.: Algebraic structures for categorial grammars, Theoretical Computer Science, 199, 1998, 5-24.
• [10] Buszkowski, W.: Type logics in grammar, in: Trends in Logic. 50 years of Studia Logica (V. F. Hendricks, J. Malinowski, Eds.), Kluwer, Dordrecht, 2003, 337-382.
• [11] Buszkowski, W., Penn, G.: Categorial Grammars Determined from Linguistic Data by Unification, Studia Logica, XLIX(4), 1990, 431-454.
• [12] Demri, S., Orłowska, E.: Incomplete Information: Structure, Inference, Complexity, EATCS Monographs in Theoretical Computer Science, Springer, 2002.
• [13] Doherty, P., Łukaszewicz, W., Skowron, A., Szałas, A.: Knowledge Representation Techniques. A Rough Set Approach, Studies in Fuzziness and Soft Computing, Springer, 2006.
• [14] Dziemidowicz, B.: Optimal Unification and Learning Algorithms for Categorial Grammars, Fundamenta Informaticae, 49, 2002, 297-308.
• [15] Fulop, S. A.: Semantic Bootstrapping of Type-Logical Grammar, Journal of Logic, Language and Information, 14, 2005, 49-86.
• [16] Gecség, F., Steinby, M.: Tree Automata, Akademiai Kiadó, Budapest, 1984.
• [17] Gold, E. M.: Language Identification in the Limit, Information and Control, 10, 1967, 447-474.
• [18] Kanazawa, M.: Identification in the Limit of Categorial Grammars, Journal of Logic, Language and Information, 5(2), 1996, 115-155.
• [19] Kanazawa, M.: Learnable Classes of Categorial Grammars, Studies in Logic, Language and Information, CSLI Publications & FoLLI, Stanford, California, 1998.
• [20] Kapur, S.: Computational Learning of Languages. Ph. D. Thesis, Cornell University, 1991.
• [21] Lambek, J.: The mathematics of sentence structure, American Mathematical Monthly, 65, 1958, 154-170.
• [22] Lambek, J.: Bilinear Logic in Algebra and Linguistics, in: Advances in Linear Logic (J. Y. Girard, Y. Lafont, L. Regnier, Eds.), Cambridge University Press, Cambridge, 1995, 43-59.
• [23] Lloyd, J. W.: Foundations of Logic Programming, Springer-Verlag, Berlin, 1987.
• [24] Marciniec, J.: Learning Categorial Grammars by Unification with Negative Constraints, Journal of Applied Non-Classical Logics, 4, 1994, 181-200.
• [25] Marciniec, J.: Infinite Set Unification with Application to Categorial Grammar, Studia Logica, LVIII(3), 1997, 339-355.
• [26] Marciniec, J.: Optimal Unification of Infinite Sets of Types, Fundamenta Informaticae, 62(3,4), 2004, 395-407.
• [27] Moortgat, M.: Categorial Type Logics, in: van Benthem and ter Meulen [5], 93-177.
• [28] Moortgat, M.: Structural Equations in Language Learning, in: Logical Aspects of Computational Linguistics (P. de Groote, G. Morrill, C. Retore, Eds.), vol. 2099 of Lecture Notes in Artificial Intelligence, Springer, 2001, 1-16.
• [29] Osherson, D., de Jongh, D., Martin, E., Weinstein, S.: Formal Learning Theory, in: van Benthem and ter Meulen [5], 737-775.
• [30] Pawlak, Z.: Rough sets, International Journal of Information and Computer Science, 11(5), 1982, 341-356.
• [31] Pawlak, Z.: Rough Sets. Theoretical Aspects of Reasoning about Data, Kluwer, Dordrecht, 1991.
• [32] Pawlak, Z., Skowron, A.: Rudiments of Rough Sets, Information Sciences, to appear.
• [33] Polkowski, L. T.: Rough Sets. Mathematical Foundations, Advances in Soft Computing, Springer, 2002.
• [34] Shinohara, T.: Inductive Inference of Monotonic Data, in: Algorithmic Learning Theory (S. Arikawa, S. Goto, S. Ohsuga, T. Yokomori, Eds.), Springer, 1990, 339-351.
• [35] Wright, K.: Identification of unions of languages drawn from an identifiable class, in: The 1989 Workshop on Computational Learning Theory, Morgan Kaufmann, San Mateo, California, 1989, 328-333.