Polynomial Time Algorithms for Learning K -Reversible Languages and Pattern Languages with Correction Queries
Abstract
We investigate two of the language classes intensively studied by the algorithmic learning theory community in the context of learning with correction queries. More precisely, we show that any pattern language can be inferred in polynomial time in length of the pattern by asking just a linear number of correction queries, and that k -reversible languages are efficiently learnable within this setting. Note that although the class of all pattern languages is learnable with membership queries, this cannot be done in polynomial time. Moreover, the class of k -reversible languages is not learnable at all using membership queries only.
Cite
Text
Tîrnauca and Knuutila. "Polynomial Time Algorithms for Learning K -Reversible Languages and Pattern Languages with Correction Queries." International Conference on Algorithmic Learning Theory, 2007. doi:10.1007/978-3-540-75225-7_23Markdown
[Tîrnauca and Knuutila. "Polynomial Time Algorithms for Learning K -Reversible Languages and Pattern Languages with Correction Queries." International Conference on Algorithmic Learning Theory, 2007.](https://mlanthology.org/alt/2007/tirnauca2007alt-polynomial/) doi:10.1007/978-3-540-75225-7_23BibTeX
@inproceedings{tirnauca2007alt-polynomial,
title = {{Polynomial Time Algorithms for Learning K -Reversible Languages and Pattern Languages with Correction Queries}},
author = {Tîrnauca, Cristina and Knuutila, Timo},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2007},
pages = {272-284},
doi = {10.1007/978-3-540-75225-7_23},
url = {https://mlanthology.org/alt/2007/tirnauca2007alt-polynomial/}
}