<テクニカルレポート>
The Learnability of Simple Deterministic Finite-Memory Automata

作成者
本文言語
出版者
発行日
収録物名
出版タイプ
アクセス権
関連DOI
関連URI
関連情報
概要 The present paper establishes the learnability of simple deterministic finitememory automata via membership and equivalence queries. Simple deterministic finite-memory automata are a subclass of deter...ministic finite-memory automata introduced by Kaminski and Francez [9] as a model generalizing finite-state automata to infinite alphabets. For arriving at a meaningful learning model we first prove the equivalence problem for simple deterministic finite-memory automata to be decidable by reducing it to the equivalence problem for finite-state automata. In particular, we present a decision algorithm taking as input any two simple deterministic finite-memory automata A and B which computes a number k from A and B as well as two finite state automata $ M_A , M_B $ over a finite alphabet $ Sigma $ of cardinality k such that A and B are equivalent iff $ M_A $ and $ M_B $ are equivalent over $ Sigma $. Next, we provide the announced learning algorithm and prove its running time to be polynomially bounded in the length of a longest counter example returned, in k, the number described above, and in n the number of states of a minimum deterministic finite state automata being consistent with the target language over a finite alphabet of cardinality k.続きを見る

本文ファイル

pdf doi-tr-127 pdf 1.23 MB 160  

詳細

レコードID
査読有無
タイプ
登録日 2009.04.22
更新日 2017.01.20