Efficient algorithms for the inference of minimum size DFAs

This work describes algorithms for the inference of minimum size determinis tic automata consistent with a labeled training set. The algorithms present ed represent the state of the art for this problem, known to be computation ally very hard. In particular, we analyze the performance of algorithms that use implicit e numeration of solutions and algorithms that perform explicit search but inc orporate a set of techniques known as dependency directed backtracking to p rune the search tree effectively. We present empirical results that show the comparative efficiency of the me thods studied and discuss alternative approaches to this problem, evaluatin g their advantages and drawbacks.