THE LEARNABILITY OF SIMPLE DETERMINISTIC FINITE-MEMORY AUTOMATA VIA QUERIES
Hiroshi Sakamoto · Bulletin of informatics and cybernetics · 1998
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.