Efficient search techniques for the inference of minimum size finite automata

Abstract

We propose a new algorithm for the inference of the minimum size deterministic automaton consistent with a prespecified set of input/output strings. Our approach improves a well known search algorithm proposed by A.W. Bierman and J.A. Feldman (1972), by incorporating a set of techniques known as dependency directed backtracking. These techniques have already been used in other applications, but we are the first to apply them to this problem. The results show that the application of these techniques yields an algorithm that is, for the problems studied, orders of magnitude faster than existing approaches.