Abstract
We show that the family \(\mathrm {S}^+_L=\{L \cup \{x\}: x \in \omega \} \cup \{L\}\) consisting of the languages obtained from a given language (i.e., computably enumerable set) L by adding at most one additional element can be explanatorily learned from informant (i.e., is \(\mathrm {InfEx}\)-learnable) if and only if L is autoreducible. Similarly, the subfamily \(\hat{\mathrm {S}}^+_L=\{L \cup \{x\}: x \not \in L\}\) of \(\mathrm {S}^+_L\) consisting of the languages obtained from L by adding exactly one additional element can be learned from informant without mind changes (i.e., is \(\mathrm {InfFin}\)-learnable) if and only if L is autoreducible.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Angluin, D.: Inductive inference of formal languages from positive data. Inf. Control 45(2), 117–135 (1980)
Barzdinš, Ja.M.: Two theorems on the identification in the limit of functions. (Russian) Latviisk. Gos. Univ. Učen. Zap. 210 Teorija Algoritmov i Programm No. 1, pp. 82–88 (1974)
Barzdinš, J., Freivalds, R.: On the prediction of general recursive functions. Sov. Math. Doklady 13, 1224–1228 (1972)
Blum, L., Blum, M.: Toward a mathematical theory of inductive inference. Inf. Control 28, 125–155 (1975)
Case, J., Lynes, C.: Machine inductive inference and language identification. Automata, Languages and Programming. LNCS, vol. 140, pp. 107–115. Springer, Berlin (1982)
Downey, R.G., Slaman, T.A.: Completely mitotic R.E. degrees. Ann. Pure Appl. Logic 41(2), 119–152 (1989)
Freivalds, R.V., Wiehagen, R.: Inductive inference with additional information. Elektron. Informationsverarb. Kybernet. 15(4), 179–185 (1979)
Gold, E.M.: Language identification in the limit. Inf. Control 10, 447–474 (1967)
Ingrassia, M.A.: P-genericity for recursively enumerable sets. Thesis (Ph.D.), University of Illinois at Urbana-Champaign, ProQuest LLC, Ann Arbor, MI, 162 p. (1981)
Jain, S., Osherson, D., Royer, J.S., Sharma, A.: Systems That Learn, An Introduction to Learning Theory, 2nd edn. The MIT Press, Cambridge (1999)
Ladner, R.E.: Mitotic recursively enumerable sets. J. Symb. Logic 38, 199–211 (1973)
Ladner, R.E.: A completely mitotic nonrecursive R.E. degree. Trans. Am. Math. Soc. 184, 479–507 (1973, 1974)
Soare, R.I.: Recursively Enumerable Sets and Degrees. A Study of Computable Functions and Computably Generated Sdets. Perspectives in Mathematical Logic. Springer, Berlin (1987). xviii+437
Stephan, F.: Recursion Theory. National University of Singapore, Lecture Notes (2012). http://www.comp.nus.edu.sg/~fstephan/recursiontheory-pstopdf.pdf
Trahtenbrot, B.A.: Autoreducibility. (Russian). Dokl. Akad. Nauk SSSR 192, 1224–1227 (1970)
Acknowledgements
We would like to thank Wolfgang Merkle for some very helpful discussions and one of the anonymous referees for his very useful comments and suggestions.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Ambos-Spies, K. (2016). Learning Finite Variants of Single Languages from Informant. In: Ortner, R., Simon, H., Zilles, S. (eds) Algorithmic Learning Theory. ALT 2016. Lecture Notes in Computer Science(), vol 9925. Springer, Cham. https://doi.org/10.1007/978-3-319-46379-7_11
Download citation
DOI: https://doi.org/10.1007/978-3-319-46379-7_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-46378-0
Online ISBN: 978-3-319-46379-7
eBook Packages: Computer ScienceComputer Science (R0)