Limits of exact algorithms for inference of minimum size finite state machines

Abstract. We address the problem of selecting the minimum sized nite state machine consistent with given input/output samples. The problem can be solved by computing the minimum nite state machine equivalent to a nite state machine without loops obtained from the training set. We compare the performance of four algorithms for this task: two algorithms for incompletely specied nite state machine reduction, an algorithm based on a well known explicit search procedure and an algorithm based on a new implicit search procedure that is introduced in this paper. 1 Introduction and Related Work We address the problem of inferring the nite state machine (FSM) with mini-mum number of states that is consistent with a given training set. This problem is important for the machine learning community because of the well known connections between hypothesis compactness and predictive accuracy