Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Journal of Logic Lan...arrow_drop_down
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
Journal of Logic Language and Information
Article . 2022 . Peer-reviewed
License: Springer Nature TDM
Data sources: Crossref
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
zbMATH Open
Article . 2023
Data sources: zbMATH Open
DBLP
Article
Data sources: DBLP
versions View all 3 versions
addClaim

This Research product is the result of merged Research products in OpenAIRE.

You have already added 0 works in your ORCID record related to the merged Research product.

Language Learnability in the Limit: A Generalization of Gold’s Theorem

Language learnability in the limit: a generalization of Gold's theorem
Authors: Fernando C. Alves;

Language Learnability in the Limit: A Generalization of Gold’s Theorem

Abstract

The author nicely reviews the early results in inductive inference and gives a good picture of these results. He considers general learners, that is, learners that are not limited by their computational abilities but only by general topological limitations of the classes to be learnt from text. Therefore some theorems which hold in inductive inference only for uniformly recursive classes are here stated and applied to all families of sets, as restrictions on the learner from the ability to compute the hypotheses are not considered. The value of this work is that the author connects the community of researchers in inductive inference with pointers to the work of \textit{R. M. Wharton} [Inf. Control 26, 236--255 (1974; Zbl 0309.68063)], \textit{K. Johnson} [Philos. Sci. 71, No. 4, 571--592 (2004; Zbl 1562.68072)] and \textit{P. Niyogi} [The computational nature of language learning and evolution. Cambridge, MA: MIT Press (2006; Zbl 1559.91002)], which has more or less been overlooked by the community. On the other hand, the author himself is not aware of most of the ongoing research in inductive inference. For example, he does not cite the main textbooks in the area, which are the two editions (they are quite different in material presented) of the textbook [\textit{D. N. Osherson} et al., Systems that learn. An introduction to learning theory for cognitive and computer scientists. Cambridge, MA: MIT Press (1985; Zbl 1559.68004); second edition by \textit{S. Jain} et al. Cambridge, MA: MIT Press (1999; Zbl 1559.68003)]. Some of the items he aims at have been investigated by other researchers in quite some depth. Also the observation that for every text \(T\) and every language \(L\) any probability distribution on all words with the overall probability of each word being positive satisfies that the probability of the symmetric differences between \(L\) and the set \(\{T(0),T(1),\ldots,T(n)\}\) goes to \(0\) is known to researchers; learning criteria based on this observation are investigated. Other notions like partial learning are not mentioned in this paper, though that learning notion fixes the shortcoming that in the usual model of Gold the class of all r.e. languages is not learnable. In summary, this is a nice article about the start of inductive inference and some more recent works overlooked in the research area; however, for getting a complete overview of the field, the interested reader should also read the two books cited above and also study more recent works by authors still active in the area of inductive inference. In particular the connections between learnability and recursion theory is not visible from the work presented here.

Related Organizations
Keywords

recursion theory, inductive inference, Computational learning theory, learning in the limit, Formal languages and automata, Word problems, etc. in computability and recursion theory, Recursive functions and relations, subrecursive hierarchies, Gold's theorem

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    1
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
1
Average
Average
Average
Upload OA version
Are you the author of this publication? Upload your Open Access version to Zenodo!
It’s fast and easy, just two clicks!