| Creator |
|
| Language |
|
| Publisher |
|
|
|
| Date |
|
| Source Title |
|
| Vol |
|
| Issue |
|
| First Page |
|
| Last Page |
|
| Publication Type |
|
| Access Rights |
|
| Crossref DOI |
|
| Related DOI |
|
|
|
| Related URI |
|
|
|
| Relation |
|
|
|
| Abstract |
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.show more
|
Export Mendeley
p093