Learning Simple Deterministic Finite-Memory Automata

Abstract

This paper establishes 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 [9] as a model generalizing finite 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, there exists 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 and M _B over a finite alphabet Σ of cardinality k such that A and B are equivalent over all alphabets iff M _A and M _B are equivalent over Σ . Next, we provide the announced learning algorithm, show its correctness, and analyze its running time. The algorithm is partially based on Angluin's [1] observation table. In particular, for every target and each finite alphabet Σ , the algorithm outputs a hypothesis that is consistent with the target over Σ . Together with the first result mentioned above, 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. Finally, the running time is estimated.