On the State Minimization of Fuzzy Automata

This paper investigates the minimization problem of fuzzy automata, aiming to obtain a procedure for finding a minimal state fuzzy automaton equivalent to a given one. The decision version of the minimization problem is as follows: Given a fuzzy automaton A and a natural number k, i.e., a pair (A, k), is there a k-state fuzzy automaton equivalent to A? We prove that the above problem is decidable for fuzzy automata over totally ordered lattices and then obtain a procedure for minimizing a given fuzzy automaton. To this end, we introduce the concept of systems of fuzzy polynomial equations, present a procedure for finding solutions of these systems and, finally, reduce the above decision problem to finding a solution of a system of fuzzy polynomial equations. It is worth pointing out that although some algorithms in the literature were claimed to be minimization algorithms, the term “minimization” there did not mean state minimization in our sense, since these algorithms did not aim at a minimal fuzzy automaton but found “reasonably” small fuzzy automata.