## ＜テクニカルレポート＞The Learnability of Simple Deterministic Finite-Memory Automata

作成者 著者識別子 作成者名 所属機関 所属機関名 Department of Informatics Kyushu University 九州大学大学院システム情報科学研究院情報理学部門 英語 Department of Informatics, Kyushu University 九州大学大学院システム情報科学研究院情報理学部門 1996-09-19 127 Accepted Manuscript open access DOI　Technical Report || 127 || p1-14 http://www.i.kyushu-u.ac.jp/research/report.html DOI　Technical Report || 127 || p1-14 http://www.i.kyushu-u.ac.jp/research/report.html DOI　Technical Report || 127 || p1-14 http://www.i.kyushu-u.ac.jp/research/report.html 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.続きを見る

### 本文ファイル

doi-tr-127 pdf 1.23 MB 160

### 詳細

レコードID 3229 査読無 テクニカルレポート 2009.04.22 2017.01.20