Abstract
It is proved that for any k, the class of classical categorial grammars that assign at most k types to each symbol in the alphabet is learnable, in the Gold (1967) sense of identification in the limit from positive data. The proof crucially relies on the fact that the concept known as finite elasticity in the inductive inference literature is preserved under the inverse image of a finite-valued relation. The learning algorithm presented here incorporates Buszkowski and Penn's (1990) algorithm for determining categorial grammars from input consisting of functor-argument structures.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ajdukiewicz, K., 1935, “Die syntaktische Konnexität”, Studia Philosophica 1, 1–27.
Angluin, D., 1980a, “Finding patterns common to a set of strings”, Journal of Computer and System Sciences 21, 46–62.
Angluin, D., 1980b, “Inductive inference of formal languages from positive data”, Information and Control 45, 117–135.
Angluin, D., 1982, “Inference of reversible languages”, Journal of the Association for Computing Machinery 29, 741–765.
Angluin, D. and Smith, C. H., 1983, “Inductive inference: theory and methods”, Computing Surveys 15, 237–269.
Barendregt, H. P., 1992, “Lambda calculi with types”, in Handbook of Logic in Computer Science, Volume 2, S. Abramsky, D. M. Gabbay, and T. S. E. Maibaum, eds., Oxford: Clarendon Press.
Bar-Hillel, Y., 1953, “A quasi-arithmetical notation for syntactic description”, Language 29, 47–58. Reprinted in Bar-Hillel 1964.
Bar-Hillel, Y., 1960, “Some linguistic obstacles to machine translation”, reprinted in Bar-Hillel 1964.
Bar-Hillel, Y., 1964, Language and Information, Reading, MA: Addison-Wesley.
Bar-Hillel, Y., Gaifman, H., and Shamir, E., 1960, “On categorial and phrase structure grammars”, The Bulletin of the Research Council of Israel, vol. 9F, 1–16. Reprinted in Bar-Hillel 1964.
Buszkowski, W., 1987a, “Solvable problems for classical categorial grammars”, Bulletin of the Polish Academy of Sciences: Mathematics 35, 373–382.
Buszkowski, W., 1987b, “Discovery procedures for categorial grammars”, in Categories, Polymorphism and Unification, E. Klein and J. van Benthem, eds., University of Amsterdam.
Buszkowski, W., 1988, “Generative power of categorial grammars”, in Categorial Grammars and Natural Language Structures, R. T. Oehrle, E. Bach, and D. Wheeler, eds., Dordrecht: Reidel.
Buszkowski, W. and Penn, G., 1990, “Categorial grammars determined from linguistic data by unification”, Studia Logica 49, 431–454.
Chomsky, N., 1986, Knowledge of Language: Its Nature, Origin, and Use, New York: Praeger.
Dowty, David. 1988. Type raising, functional composition, and non-constituent conjunction. In Richard T. Oehrle, Emmon Bach, and Deirdre Wheeler, eds., Categorial Grammars and Natural Language Structures, Dordrecht: Reidel.
Gold, M. E., 1967, “Language identification in the limit”, Information and Control 10, 447–474.
de Jongh, D. and Kanazawa, M., 1995, Learnability Theory, course material presented at the Seventh Summer School in Logic, Language and Information, University of Barcelona, August 1995.
Kanazawa, M., 1994a, Learnable Classes of Categorial Grammars, Ph.D. dissertation, Stanford University. Available as ILLC Dissertation Series 1994–8, Institute for Logic, Language, and Computation, University of Amsterdam (illc@fwi.uva.nl).
Kanazawa, M., 1994b, “A note on language classes with finite elasticity”, Reprot CS-R9471, CWI, Amsterdam.
Kapur, S., 1991, Computational Learning of Languages, Ph.D. dissertation, Cornell University. Available as Technical Report 91-1234, Department of Computer Science, Cornell University.
Kearns, M. J. and Vazirani, U. V., 1994, An Introduction to Computational Learning Theory, Cambridge, Mass.: MIT Press.
Lambek, J., 1958, “The mathematics of sentence structure”, American Mathematical Monthly 65, 154–170. Reprinted in Categorial Grammars, W. Buszkowski, W. Marciszewski, and J. van Benthem, eds., Amsterdam: John Benjamins, 1988.
Lambek, J., 1961, “On the calculus of syntactic types”, in Structure of Language and its Mathematical Aspects, R. Jakobson, ed., Providence, R.I.: American Mathematical Society.
Lassez, J.-L., M. J. Maher, and K. Marriott. 1988. Unification revisited. In J. Minker, ed., Foundations of Deductive Databases and Logic Programming, pp. 587–625. Los Altos, Calif.: Morgan Kaufmann.
Levy, Leon S. and Aravind K. Joshi. 1978. Skeletal structural descriptions. Information and Control 39, 192–211.
Montague, R., 1973. “The proper treatment of quantification in ordinary English”, reprinted in Formal Philosophy: Selected Papers of Richard Montague, R. H. Thomason, ed., New Haven: Yale University Press, 1974.
Moriyama, T. and Sato, M, 1993, “Properties of language classes with finite elasticity”, in Algorithmic Learning Theory, Proceedings, 1993, K. P. Jankte, S. Kobayashi, E. Tomita, and T. Yokomori, eds., Lecture Notes in Artificial Intelligence 744, Berlin: Springer.
Motoki, T., Shinohara, T., and Wright, K., 1991, “The correct definition of finite elasticity: Corrigendum to identification of unions”, p. 375 in The Fourth Annual Workshop on Computational Learning Theory, San Mateo, CA: Morgan Kaufmann.
Osherson, D., Stob, M., and Weinstein, S., 1986, Systems That Learn, Cambridge, MA: MIT Press.
Osherson, D., Weinstein, S., de Jongh, D., and Martin, E., 1994, “Formal learning theory”, to appear in Handbook of Logic and Language, J. van Benthem and A. ter Meulen, eds.
Sakakibara, Y., 1992, “Efficient learning of context-free grammars from positive structural examples”, Information and Computation 97, 23–60.
Shinohara, T., 1990a, “Inductive inference from positive data is powerful”, pp. 97–110 in The 1990 Workshop on Computational Learning Theory, San Mateo, CA: Morgan Kaufmann.
Shinohara, T., 1990b, “Inductive inference of monotonic formal systems from positive data”, pp. 339–351 in Algorithmic Learning Theory, S. Arikawa, S. Goto, S. Ohsuga, and T. Yokomori, eds., Tokyo: Ohmsha, and New York and Berlin: Springer.
Steedman, Mark J. 1985. Dependency and coordination in the grammar of Dutch and English. Language 61, 523–568.
Steedman, Mark J. 1987. Combinatory grammars and parasitic gaps. Natural Language and Linguistic Theory 5, 403–440.
Steedman, Mark J. 1988. Combinators and grammars. In Richard T. Oehrle, Emmon Bach, and Deirdre Wheeler, eds., Categorial Grammars and Natural Language Structures. Dordrecht: Reidel.
Wexler, K. and Culicover, P., 1980, Formal Principles of Language Acquisition, Cambridge, MA: MIT Press.
Wright, K., 1989, “Identification of unions of languages drawn from an identifiable class”, pp. 328–333 in The 1989 Workshop on Computational Learning Theory, San Mateo, CA: Morgan Kaufmann.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Kanazawa, M. Identification in the limit of categorial grammars. J Logic Lang Inf 5, 115–155 (1996). https://doi.org/10.1007/BF00173697
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF00173697