In this paper, we deal with minimization of finite automata associated with finite languages all the words have the same length. This problem arises in the context of Constraint Satisfaction Problems, widely used in AI. We first give some complexity results which are based on the strong relationship with covering problems of bipartite graphs. We then use these coverings as a basic tool for the definition of minimization heuristics, and describe some experimental results.
['Jérôme Amilhastre', 'Philippe Janssen', 'Marie-Catherine Vilarem']
FA minimisation heuristics for a class of finite languages