Abstract
The object of investigation in this paper is the learnability of co-recursively enumerable (co-r.e.) languages based on Gold’s [11] original model of inductive inference. In particular, the following learning models are studied: finite learning, explanatory learning, vacillatory learning and behaviourally correct learning. The relative effects of imposing further learning constraints, such as conservativeness and prudence on these various learning models are also investigated. Moreover, an extension of Angluin’s [1] characterisation of identifiable indexed families of recursive languages to families of conservatively learnable co-r.e. classes is presented. In this connection, the paper considers the learnability of indexed families of recursive languages, uniformly co-r.e. classes as well as other general classes of co-r.e. languages. A containment hierarchy of co-r.e. learning models is thereby established; while this hierarchy is quite similar to its r.e. analogue, there are some surprising collapses when using a co-r.e. hypothesis space; for example vacillatory learning collapses to explanatory learning.
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
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Angluin, D.: Inductive inference of formal languages from positive data. Information and Control 45(2), 117–135 (1980)
Baliga, G., Case, J., Jain, S.: The synthesis of language learners. Information and Computation 152, 16–43 (1999)
Bārzdiņš, J., Freivalds, R.: On the prediction of general recursive functions. Soviet Mathematical Doklady 13, 1224–1228 (1972)
Blum, L., Blum, M.: Towards a mathematical theory of inductive inference. Information and Control 28, 125–155 (1975)
Carlucci, L., Case, J., Jain, S.: Learning correction grammars. The Journal of Symbolic Logic 74, 489–516 (2009)
Case, J.: The power of vacillation in language learning. SIAM Journal on Computing 28(6), 1941–1969 (1999)
Case, J., Jain, S., Sharma, A.: On learning limiting programs. International Journal of Foundations of Computer Science 3, 93–115 (1992)
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)
Freibergs, V., Tulving, E.: The effect of practice on utilization of information from positive and negative instances in concept identification. Canadian Journal of Psychology 15(2), 101–106 (1961)
Fulk, M.A.: Prudence and other conditions on formal language learning. Information and Computation 85(1), 1–11 (1990)
Gold, E.M.: Language identification in the limit. Information and Control 10, 447–474 (1967)
Jain, S., Stephan, F., Ye, N.: Prescribed learning of r.e. classes. Theoretical Computer Science 410(19), 1796–1806 (2009)
Jongh, D.D., Kanazawa, M.: Angluin’s theorem for indexed families of r.e. sets and applications. In: COLT, pp. 193–204 (1996)
Krebs, M.J., Lovelace, E.A.: Disjunctive concept identification: stimulus complexity and positive versus negative instances. Journal of Verbal Learning and Verbal Behaviour 9, 653–657 (1970)
Lange, S., Zeugmann, T.: Set-driven and rearrangement-independent learning of recursive languages. Mathematical Systems Theory 29(6), 599–634 (1996)
Lange, S., Zeugmann, T., Kapur, S.: Characterizations of monotonic and dual monotonic language learning. Information and Computation 120(2), 155–173 (1995)
Lange, S., Zeugmann, T., Zilles, S.: Learning indexed families of recursive languages from positive data: a survey. Theoretical Computer Science 397(1-3), 194–232 (2008)
Osherson, D., Stob, M., Weinstein, S.: Learning strategies. Information and Control 53, 32–51 (1982)
Popper, K.R.: Conjectures and refutations: the growth of scientific knowledge. Routledge and Kegan Paul, London (1972)
Rogers Jr., H.: Theory of recursive functions and effective computability. MIT Press, Cambridge (1987)
Zeugmann, T., Lange, S.: A Guided Tour Across the Boundaries of Learning Recursive Languages. In: Lange, S., Jantke, K.P. (eds.) GOSLER 1994. LNCS, vol. 961, pp. 190–258. Springer, Heidelberg (1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gao, Z., Stephan, F. (2012). Learnability of Co-r.e. Classes. In: Dediu, AH., Martín-Vide, C. (eds) Language and Automata Theory and Applications. LATA 2012. Lecture Notes in Computer Science, vol 7183. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-28332-1_22
Download citation
DOI: https://doi.org/10.1007/978-3-642-28332-1_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-28331-4
Online ISBN: 978-3-642-28332-1
eBook Packages: Computer ScienceComputer Science (R0)