Learning Finite Variants of Single Languages from Informant
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.
Cite
Text
Ambos-Spies. "Learning Finite Variants of Single Languages from Informant." International Conference on Algorithmic Learning Theory, 2016. doi:10.1007/978-3-319-46379-7_11Markdown
[Ambos-Spies. "Learning Finite Variants of Single Languages from Informant." International Conference on Algorithmic Learning Theory, 2016.](https://mlanthology.org/alt/2016/ambosspies2016alt-learning/) doi:10.1007/978-3-319-46379-7_11BibTeX
@inproceedings{ambosspies2016alt-learning,
title = {{Learning Finite Variants of Single Languages from Informant}},
author = {Ambos-Spies, Klaus},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2016},
pages = {163-173},
doi = {10.1007/978-3-319-46379-7_11},
url = {https://mlanthology.org/alt/2016/ambosspies2016alt-learning/}
}