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.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 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
Berger, J., et al.: Learning languages with decidable hypotheses. CoRR (2020)
Blum, L., Blum, M.: Toward a mathematical theory of inductive inference. Inf. Control 28, 125–155 (1975)
Blum, M.: A machine-independent theory of the complexity of recursive functions. J. ACM 14, 322–336 (1967)
Carlucci, L., Case, J., Jain, S., Stephan, F.: Results on memory-limited U-shaped learning. Inf. Comput. 205, 1551–1573 (2007)
Case, J., Kötzing, T.: Strongly non-U-shaped language learning results by general techniques. Inf. Comput. 251, 1–15 (2016)
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
Doskoč, V., Kötzing, T.: Cautious limit learning. In: Proceedings of the International Conference on Algorithmic Learning Theory (ALT) (2020)
Fulk, M.: A Study of Inductive Inference Machines. Ph.D. thesis (1985)
Fulk, M.A.: Prudence and other conditions on formal language learning. Inf. Comput. 85, 1–11 (1990)
Gold, E.M.: Language identification in the limit. Inf. Control 10, 447–474 (1967)
Jain, S., Osherson, D., Royer, J.S., Sharma, A.: Systems that Learn: An Introduction to Learning Theory. MIT Press, Cambridge, Second Edition (1999)
Kinber, E.B., Stephan, F.: Language learning from texts: Mindchanges, limited memory, and monotonicity. Inf. Comput. 123, 224–241 (1995)
Kötzing, T., Palenta, R.: A map of update constraints in inductive inference. Theoret. Comput. Sci. 650, 4–24 (2016)
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)
Kötzing, T.: Abstraction and Complexity in Computational Learning in the Limit. Ph.D. thesis, University of Delaware (2009)
Lange, S., Zeugmann, T., Zilles, S.: Learning indexed families of recursive languages from positive data: A survey. Theor. Comput. Sci. 397, 194–232 (2008)
Osherson, D.N., Weinstein, S.: Criteria of language learning. Inf. Control 52, 123–138 (1982)
Rogers, H., Jr.: Theory of Recursive Functions and Effective Computability. MIT Press, Cambridge (1987)
Schäfer-Richter, G.: Über Eingabeabhängigkeit und Komplexität von Inferenzstrategien. Ph.D. thesis, RWTH Aachen University, Germany (1984)
Wexler, K., Culicover, P.W.: Formal Principles of Language Acquisition. MIT Press, Cambridge (1980)
Wiehagen, R.: Limes-Erkennung rekursiver Funktionen durch spezielle Strategien. J. Inf. Proc. Cybern. 12, 93–99 (1976)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
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)