Inductive Inference with Bounded Mind Changes
Abstract
In this paper, we deal with inductive inference for a class of recursive languages with a bounded number of mind changes. We introduce an n -bounded finite tell-tale and a pair of n -bounded finite tell-tales of a language, and present a necessary and sufficient condition for a class to be inferable with bounded mind changes, when the equivalence of any two languages in the class is effectively decidable. We also show that the inferability of a class from positive data strictly increases, when the allowed number of mind changes increases. In his previous paper, Mukouchi gave necessary and sufficient conditions for a class of recursive languages to be finitely identifiable, that is, to be inferable without any mind changes from positive or complete data. The results we present in this paper are natural extensions of the above results.
Cite
Text
Mukouchi. "Inductive Inference with Bounded Mind Changes." International Conference on Algorithmic Learning Theory, 1992. doi:10.1007/3-540-57369-0_33Markdown
[Mukouchi. "Inductive Inference with Bounded Mind Changes." International Conference on Algorithmic Learning Theory, 1992.](https://mlanthology.org/alt/1992/mukouchi1992alt-inductive/) doi:10.1007/3-540-57369-0_33BibTeX
@inproceedings{mukouchi1992alt-inductive,
title = {{Inductive Inference with Bounded Mind Changes}},
author = {Mukouchi, Yasuhito},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {1992},
pages = {125-134},
doi = {10.1007/3-540-57369-0_33},
url = {https://mlanthology.org/alt/1992/mukouchi1992alt-inductive/}
}