Locality, Reversibility, and Beyond: Learning Languages from Positive Data
Abstract
In algorithmic learning theory fundamental roles are played by the family of languages that are locally testable in the strict sense and by the family of reversible languages. These two families are shown to be the first two members of an infinite sequence of families of regular languages the members of which are learnable in the limit from positive data only. A uniform procedure is given for deciding, for each regular language R and each of our specified families, whether R belongs to the family. The approximation of arbitrary regular languages by languages belonging to these families is discussed. Further, we will give a uniform scheme for learning these families from positive data. Several research problems are also suggested.
Cite
Text
Head et al. "Locality, Reversibility, and Beyond: Learning Languages from Positive Data." International Conference on Algorithmic Learning Theory, 1998. doi:10.1007/3-540-49730-7_15Markdown
[Head et al. "Locality, Reversibility, and Beyond: Learning Languages from Positive Data." International Conference on Algorithmic Learning Theory, 1998.](https://mlanthology.org/alt/1998/head1998alt-locality/) doi:10.1007/3-540-49730-7_15BibTeX
@inproceedings{head1998alt-locality,
title = {{Locality, Reversibility, and Beyond: Learning Languages from Positive Data}},
author = {Head, Tom and Kobayashi, Satoshi and Yokomori, Takashi},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {1998},
pages = {191-204},
doi = {10.1007/3-540-49730-7_15},
url = {https://mlanthology.org/alt/1998/head1998alt-locality/}
}