<学術雑誌論文>
THE LEARNABILITY OF SIMPLE DETERMINISTIC FINITE-MEMORY AUTOMATA VIA QUERIES

作成者
本文言語
出版者
発行日
収録物名
開始ページ
終了ページ
出版タイプ
アクセス権
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.続きを見る

本文ファイル

pdf p093 pdf 1.05 MB 300  

詳細

PISSN
EISSN
NCID
レコードID
査読有無
タイプ
登録日 2009.04.22
更新日 2020.10.22

この資料を見た人はこんな資料も見ています