Learning Strongly Deterministic Even Linear Languages from Positive Examples
Abstract
We consider the problem of learning deterministic even linear languages from positive examples. By a “deterministic” even linear language we mean a language generated by an LR(k) even linear grammar. We introduce a natural subclass of LR(k) even linear languages, called LR(k) in the strong sense , and show that this subclass is learnable in the limit from positive examples. Furthermore, we propose a learning algorithm that identifies this subclass in the limit with almost linear time in updating conjectures. As a corollary, in terms of even linear grammars, we have a learning algorithm for k -reversible languages that is more efficient than the one proposed by Angluin[Ang82].
Cite
Text
Koshiba et al. "Learning Strongly Deterministic Even Linear Languages from Positive Examples." International Conference on Algorithmic Learning Theory, 1995. doi:10.1007/3-540-60454-5_27Markdown
[Koshiba et al. "Learning Strongly Deterministic Even Linear Languages from Positive Examples." International Conference on Algorithmic Learning Theory, 1995.](https://mlanthology.org/alt/1995/koshiba1995alt-learning/) doi:10.1007/3-540-60454-5_27BibTeX
@inproceedings{koshiba1995alt-learning,
title = {{Learning Strongly Deterministic Even Linear Languages from Positive Examples}},
author = {Koshiba, Takeshi and Mäkinen, Erkki and Takada, Yuji},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {1995},
pages = {41-54},
doi = {10.1007/3-540-60454-5_27},
url = {https://mlanthology.org/alt/1995/koshiba1995alt-learning/}
}