Characterization and computation of approximate bisimulations for fuzzy automata

Approximate bisimulations for fuzzy automata have recently drawn attention of researches, since they allow to correlate different fuzzy automata which behave equivalently only to the chosen degree. This is of a particular interest in the state reduction of fuzzy automata, since it allows us to find a fuzzy automaton with a much smaller number of states and a slightly different behaviour from the original fuzzy automaton. The contribution of this paper is twofold. First, we study special types of approximate bisimulations which allow us to correlate all elements from both sets of states of two fuzzy automata. We show their properties, and particularly that they induce the so-called approximate isomorphism between the corresponding factor fuzzy automata. We pay a special attention to similarities and differences between homotypic and heterotypic approximate bisimulations. Second, we provide an efficient algorithm with the complexity for computing the greatest -approximate bisimulation between two finite fuzzy automata over the Gödel structure (if it exists), where is the threshold for approximation, is the number of states and is the number of non-zero transitions of the automata. This algorithm gives a great reduction of complexity when compared to the previously developed one, which has the complexity . We also design an algorithm with the complexity for computing the greatest such that there exists a -approximate bisimulation between two given finite fuzzy automata over the Gödel structure.