10月12日：李永明

For the purpose of reducing the number of states of fuzzy automata,  we study approximate bisimulations of fuzzy automata under fuzzy  similarity measures, which are induced by residuums of left-continuous  t-norms. For a real number $\alpha\in [0,1]$ and a fuzzy similarity  measure $S$, we define $\alpha$-approximate bisimulation under $S$  between two fuzzy automata and prove that the degree of similarity  between them is more than or equal to $\alpha$ if there exists an  $\alpha$-approximate bisimulation between them. Furthermore, we put forward the notion of surjective functional $\alpha$-approximate  bisimulations between two fuzzy automata under $S$. Using the notion of surjective functional $\alpha$-approximate bisimulations under $S$, the $\alpha$-approximate bisimulations for a fuzzy automaton under $S$ is defined as an equivalence relation with two additional properties.  According to an $\alpha$-approximate bisimulation for a fuzzy automaton, an aggregated fuzzy automaton has been constructed and the degree of similarity between them is also more than or equal to $\alpha$.  It is significant for us to find that there might not possess the greatest $\alpha$-approximate bisimulation for a fuzzy automaton, and we provide a polynomial-time algorithm for computing all maximal $\alpha$-approximate bisimulations. Finally, we provide the conditions of the existence of the greatest $\alpha$-approximate bisimulation.

www.sei.ecnu.edu.cn Copyright School of Computer Science and Software Engineering