Computation of the greatest simulations and bisimulations between fuzzy automata

Abstract

Recently, two types of simulations (forward and backward simulations) and four types of bisimulations (forward, backward, forward-backward, and backward-forward bisimulations) between fuzzy automata have been introduced. If there is at least one simulation/bisimulation of some of these types between the given fuzzy automata, it has been proved that there is the greatest simulation/bisimulation of this kind. In the present paper, for any of the above-mentioned types of simulations/bisimulations we provide an efficient algorithm for deciding whether there is a simulation/bisimulation of this type between the given fuzzy automata, and for computing the greatest one, whenever it exists. The algorithms are based on the method developed in Ignjatović et al. [On the greatest solutions to weakly linear systems of fuzzy relation inequalities and equations, Fuzzy Sets Syst. 161 (2010) 3081-3113], which comes down to the computing of the greatest post-fixed point, contained in a given fuzzy relation, of an isotone function on the lattice of fuzzy relations. © 2012 Elsevier B.V.