Language Learning from Membership Queries and Characteristic Examples
Abstract
This paper introduces the notion of characteristic examples and shows that the notion contributes to language learning in polynomial time. A characteristic example of a language L is an element of L which includes, in a sense, sufficient information to represent L . Every context-free language can be divided into a finite number of languages each of which has a characteristic example and it is decidable whether or not a context-free language has a characteristic example. We present an algorithm that learns parenthesis languages using membership queries and characteristic examples. Our algorithm runs in time polynomial in the number of production rules of a minimal parenthesis grammar and in the length of the longest characteristic example.
Cite
Text
Sakamoto. "Language Learning from Membership Queries and Characteristic Examples." International Conference on Algorithmic Learning Theory, 1995. doi:10.1007/3-540-60454-5_28Markdown
[Sakamoto. "Language Learning from Membership Queries and Characteristic Examples." International Conference on Algorithmic Learning Theory, 1995.](https://mlanthology.org/alt/1995/sakamoto1995alt-language/) doi:10.1007/3-540-60454-5_28BibTeX
@inproceedings{sakamoto1995alt-language,
title = {{Language Learning from Membership Queries and Characteristic Examples}},
author = {Sakamoto, Hiroshi},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {1995},
pages = {55-65},
doi = {10.1007/3-540-60454-5_28},
url = {https://mlanthology.org/alt/1995/sakamoto1995alt-language/}
}