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

Learning Languages with Decidable Hypotheses

  • Conference paper
  • First Online:
Connecting with Computability (CiE 2021)

Abstract

In language learning in the limit, the most common type of hypothesis is to give an enumerator for a language, a W-index. These hypotheses have the drawback that even the membership problem is undecidable. In this paper, we use a different system which allows for naming arbitrary decidable languages, namely programs for characteristic functions (called C-indices). These indices have the drawback that it is now not decidable whether a given hypothesis is even a legal C-index.

In this first analysis of learning with C-indices, we give a structured account of the learning power of various restrictions employing C-indices, also when compared with W-indices. We establish a hierarchy of learning power depending on whether C-indices are required (a) on all outputs; (b) only on outputs relevant for the class to be learned or (c) only in the limit as final, correct hypotheses. We analyze all these questions also in relation to the mode of data presentation.

Finally, we also ask about the relation of semantic versus syntactic convergence and derive the map of pairwise relations for these two kinds of convergence coupled with various forms of data presentation.

This work was supported by DFG Grant Number KO 4635/1-1.

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

Access this chapter

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 35.99
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 44.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    \(\mathbf {Txt}\) stands for learning from a text of positive examples; \(\mathbf {G}\) for Gold, indicating full-information learning; \(\mathbf {Ex}\) stands for explanatory.

References

  1. Berger, J., et al.: Learning languages with decidable hypotheses. CoRR (2020)

    Google Scholar 

  2. Blum, L., Blum, M.: Toward a mathematical theory of inductive inference. Inf. Control 28, 125–155 (1975)

    Article  MathSciNet  Google Scholar 

  3. Blum, M.: A machine-independent theory of the complexity of recursive functions. J. ACM 14, 322–336 (1967)

    Article  MathSciNet  Google Scholar 

  4. Carlucci, L., Case, J., Jain, S., Stephan, F.: Results on memory-limited U-shaped learning. Inf. Comput. 205, 1551–1573 (2007)

    Article  MathSciNet  Google Scholar 

  5. Case, J., Kötzing, T.: Strongly non-U-shaped language learning results by general techniques. Inf. Comput. 251, 1–15 (2016)

    Article  MathSciNet  Google Scholar 

  6. Case, J., Lynes, C.: Machine inductive inference and language identification. In: Nielsen, M., Schmidt, E.M. (eds.) ICALP 1982. LNCS, vol. 140, pp. 107–115. Springer, Heidelberg (1982). https://doi.org/10.1007/BFb0012761

    Chapter  MATH  Google Scholar 

  7. Doskoč, V., Kötzing, T.: Cautious limit learning. In: Proceedings of the International Conference on Algorithmic Learning Theory (ALT) (2020)

    Google Scholar 

  8. Fulk, M.: A Study of Inductive Inference Machines. Ph.D. thesis (1985)

    Google Scholar 

  9. Fulk, M.A.: Prudence and other conditions on formal language learning. Inf. Comput. 85, 1–11 (1990)

    Article  MathSciNet  Google Scholar 

  10. Gold, E.M.: Language identification in the limit. Inf. Control 10, 447–474 (1967)

    Article  MathSciNet  Google Scholar 

  11. Jain, S., Osherson, D., Royer, J.S., Sharma, A.: Systems that Learn: An Introduction to Learning Theory. MIT Press, Cambridge, Second Edition (1999)

    Google Scholar 

  12. Kinber, E.B., Stephan, F.: Language learning from texts: Mindchanges, limited memory, and monotonicity. Inf. Comput. 123, 224–241 (1995)

    Article  MathSciNet  Google Scholar 

  13. Kötzing, T., Palenta, R.: A map of update constraints in inductive inference. Theoret. Comput. Sci. 650, 4–24 (2016)

    Article  MathSciNet  Google Scholar 

  14. Kötzing, T., Schirneck, M., Seidel, K.: Normal forms in semantic language identification. In: Proceedings of the International Conference on Algorithmic Learning Theory (ALT), pp. 76:493–76:516 (2017)

    Google Scholar 

  15. Kötzing, T.: Abstraction and Complexity in Computational Learning in the Limit. Ph.D. thesis, University of Delaware (2009)

    Google Scholar 

  16. Lange, S., Zeugmann, T., Zilles, S.: Learning indexed families of recursive languages from positive data: A survey. Theor. Comput. Sci. 397, 194–232 (2008)

    Article  MathSciNet  Google Scholar 

  17. Osherson, D.N., Weinstein, S.: Criteria of language learning. Inf. Control 52, 123–138 (1982)

    Article  MathSciNet  Google Scholar 

  18. Rogers, H., Jr.: Theory of Recursive Functions and Effective Computability. MIT Press, Cambridge (1987)

    Google Scholar 

  19. Schäfer-Richter, G.: Über Eingabeabhängigkeit und Komplexität von Inferenzstrategien. Ph.D. thesis, RWTH Aachen University, Germany (1984)

    Google Scholar 

  20. Wexler, K., Culicover, P.W.: Formal Principles of Language Acquisition. MIT Press, Cambridge (1980)

    Google Scholar 

  21. Wiehagen, R.: Limes-Erkennung rekursiver Funktionen durch spezielle Strategien. J. Inf. Proc. Cybern. 12, 93–99 (1976)

    MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Vanja Doskoč .

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2021 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Berger, J. et al. (2021). Learning Languages with Decidable Hypotheses. In: De Mol, L., Weiermann, A., Manea, F., Fernández-Duque, D. (eds) Connecting with Computability. CiE 2021. Lecture Notes in Computer Science(), vol 12813. Springer, Cham. https://doi.org/10.1007/978-3-030-80049-9_3

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-80049-9_3

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-80048-2

  • Online ISBN: 978-3-030-80049-9

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics