| 作成者 |
|
| 本文言語 |
|
| 出版者 |
|
|
|
| 発行日 |
|
| 収録物名 |
|
| 巻 |
|
| 出版タイプ |
|
| アクセス権 |
|
| 関連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.続きを見る
|
Mendeley出力
doi-tr-127