| 作成者 |
|
| 本文言語 |
|
| 出版者 |
|
|
|
| 発行日 |
|
| 収録物名 |
|
| 巻 |
|
| 号 |
|
| 開始ページ |
|
| 終了ページ |
|
| 出版タイプ |
|
| アクセス権 |
|
| Crossref DOI |
|
| 関連DOI |
|
|
|
| 関連URI |
|
|
|
| 関連情報 |
|
|
|
| 概要 |
In this paper, we establish the learnability of simple deterministic finite-memory automata via membership and equivalence queries. Simple deterministic finite-memory automata are a subclass of finite...-memory automata introduced by Kaminski and Francez (1994) as a model generalizing finite automata to infinite alphabets. Continuously, Sakamoto and Ikeda investigated several decision problems for finite-memory automata as well as for the deterministic class. By this result, we can arrive at a meaningful learning model for simple deterministic finite-memory automata. We provide the announced learning algorithm, show its correctness, and analyze its running time. The algorithm is partially based on Angluin's (1987) observation table. In particular, for every target and each finite alphabet $ Sigma $, the algorithm outputs a hypothesis that is consistent with the target over $ Sigma $. Finally, we obtain the main result of this paper, i.e., the class of simple deterministic finite-memory automata is exactly learnable via membership and equivalence queries.続きを見る
|
Mendeley出力
