[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

On Limit Points for Some Variants of Rigid Lambek Grammars

  • Conference paper
  • First Online:
Grammatical Inference: Algorithms and Applications (ICGI 2002)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 2484))

Included in the following conference series:

  • 325 Accesses

Abstract

In this paper we give some learnability results in the field of categorial grammars. We show that in contrast to k-valued classical categorial grammars, different classes of Lambek grammars are not learnable from strings following Gold’s model. The results are obtained by the construction of limit points in each considered class: non associative Lambek grammars with empty sequences and Lambek grammars without empty sequences and without product. Such results express the difficulty of learning categorial grammars from unstructured strings and the need for structured examples.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Dana Angluin. Inductive inference of formal languages from positive data. Information and Control, 45:117–135, 1980.

    Article  MATH  MathSciNet  Google Scholar 

  2. Y. Bar-Hillel. A quasi arithmetical notation for syntactic description. Language, 29:47–58, 1953.

    Article  Google Scholar 

  3. Roberto Bonato and Christian Retoré. Learning rigid lambek grammars and minimalist grammars from structured sentences. Third workshop on Learning Language in Logic, Strasbourg, 2001.

    Google Scholar 

  4. W. Buszkowski. Mathematical linguistics and proof theory. In van Benthem and ter Meulen [vBtM97], chapter 12, pages 683–736.

    Chapter  Google Scholar 

  5. Claudia Casadio. Semantic categories and the development of categorial grammars. In R. Oehrle, E. Bach, and D. Wheeler, editors, Categorial Grammars and Natural Language Structures, pages 95–124. Reidel, Dordrecht, 1988.

    Google Scholar 

  6. C. Costa Florêncio. Consistent Identification in the Limit of the Class k-valued is NP-hard. In LACL, 2001.

    Google Scholar 

  7. Dudau-Sofronie, Tellier, and Tommasi. Learning categorial grammars from semantic types. In 13th Amsterdam Colloquium, 2001.

    Google Scholar 

  8. Annie Foret and Yannick Le Nir. Rigid lambek grammars are not learnable from strings. Coling 2002. http://www.irisa.fr/prive/foret/learn.ps.

  9. E.M. Gold. Language identification in the limit. Information and control, 10:447–474, 1967.

    Article  MATH  Google Scholar 

  10. Makoto Kanazawa. Learnable classes of categorial grammars. Studies in Logic, Language and Information. FoLLI & CSLI, 1998. distributed by Cambridge University Press.

    Google Scholar 

  11. Joachim Lambek. The mathematics of sentence structure. American mathematical monthly, 65:154–169, 1958.

    Article  MATH  MathSciNet  Google Scholar 

  12. Michael Moortgat. Categorial type logic. In van Benthem and ter Meulen [vBtM97], chapter 2, pages 93–177.

    Chapter  Google Scholar 

  13. Jacques Nicolas. Grammatical inference as unification. Rapport de Recherche RR-3632, INRIA, 1999. http://www.inria.fr/RRRT/publications-eng.html.

  14. Mati Pentus. Lambek grammars are context-free. In Logic in Computer Science. IEEE Computer Society Press, 1993.

    Google Scholar 

  15. T. Shinohara. Inductive inference from positive data is powerful. In The 1990 Workshop on Computational Learning Theory, pages 97–110, San Mateo, California, 1990. Morgan Kaufmann.

    Google Scholar 

  16. J. van Benthem and A. ter Meulen, editors. Handbook of Logic and Language. North-Holland Elsevier, Amsterdam, 1997.

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. IRISA, Campus de Beaulieu, 35042, Rennes, France

    Annie Foret & Yannick Le Nir

Authors
  1. Annie Foret
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yannick Le Nir
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Perot Systems Nederland B.V., Hoefseweg 1, 3821 AE, Amersfoort, The Netherlands

    Pieter Adriaans (Senior Research Advisor, Professor of Learning and Adaptive Systems) (Senior Research Advisor, Professor of Learning and Adaptive Systems)

  2. ILLC/Computation and Complexity Theory, Universiteit van Amsterdam, Plantage Muidergracht 24, 1018 TV, Amsterdam, The Netherlands

    Pieter Adriaans (Senior Research Advisor, Professor of Learning and Adaptive Systems) (Senior Research Advisor, Professor of Learning and Adaptive Systems)

  3. School of Electrical Engineering and Computer Science, University of Newcastle, University Drive, Callaghan, NSW, 2308, Australia

    Henning Fernau

  4. Wilhelm-Schickard-Institut für Informatik, Universität Tübingen, Sand 13, 72076, Tübingen, Germany

    Henning Fernau

  5. FNWI/ILLC, Cognitive Systems and Information Processing Group, Universiteit van Amsterdam, Room B-5.39, Nieuwe Achtergracht 166, 1018 WV, Amsterdam, The Netherlands

    Menno van Zaanen

Rights and permissions

Reprints and permissions

Copyright information

© 2002 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Foret, A., Le Nir, Y. (2002). On Limit Points for Some Variants of Rigid Lambek Grammars. In: Adriaans, P., Fernau, H., van Zaanen, M. (eds) Grammatical Inference: Algorithms and Applications. ICGI 2002. Lecture Notes in Computer Science(), vol 2484. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45790-9_9

Download citation

  • DOI: https://doi.org/10.1007/3-540-45790-9_9

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-44239-4

  • Online ISBN: 978-3-540-45790-9

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation