THE LEARNABILITY OF SIMPLE DETERMINISTIC FINITE-MEMORY AUTOMATA VIA QUERIES

In this paper, we establish the learnability of simple deterministic finitememory automata via membership and equivalence queries. Sim ple deterministic fmitememory automata are a subclass of finitememory automata introduced by Kaminski and Francez (1994) as a model gen eralizing finite automata to infinite alphabets. Continuously, Sakamoto and Ikeda investigated several decision problems for finitememory au tomata 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 cor rectness, 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 E, the algorithm outputs a hypothesis that is consistent with the target over E. 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.