On Learning Systolic Languages
Abstract
We study the learning problem of systolic languages from queries and counterexamples. A systolic language is specified by a systolic automaton which is a kind of network consisting of uniformly connected processors(finite automata). In this article, we show that the class of binary systolic tree languages is learnable in polynomial time from the learning protocol what is called minimally adequate teacher. Since the class of binary systolic tree languages properly contains the class of regular languages, the main result in this paper gives a generalization of the corresponding Angluin's result for regular languages.
Cite
Text
Yokomori. "On Learning Systolic Languages." International Conference on Algorithmic Learning Theory, 1992. doi:10.1007/3-540-57369-0_26Markdown
[Yokomori. "On Learning Systolic Languages." International Conference on Algorithmic Learning Theory, 1992.](https://mlanthology.org/alt/1992/yokomori1992alt-learning/) doi:10.1007/3-540-57369-0_26BibTeX
@inproceedings{yokomori1992alt-learning,
title = {{On Learning Systolic Languages}},
author = {Yokomori, Takashi},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {1992},
pages = {41-52},
doi = {10.1007/3-540-57369-0_26},
url = {https://mlanthology.org/alt/1992/yokomori1992alt-learning/}
}