We introduce depth-bounded fuzzy bisimulation between fuzzy Kripke models. Roughly speaking, a depth-bounded fuzzy bisimulation is a decreasing sequence of fuzzy binary relations whose infimum is a fuzzy bisimulation. We provide logical characterizations of depth-bounded fuzzy bisimulations between fuzzy Kripke models w.r.t. a fuzzy multimodal logic fK over complete residuated lattices, including fuzzy invariance of formulas of fK with a modal depth bounded by n under the nth component of a depth-bounded fuzzy bisimulation, as well as the Hennessy-Milner property of depth-bounded fuzzy bisimulations. We also provide a polynomial-time algorithm for computing the nth component of the greatest depth-bounded fuzzy bisimulation between two finite fuzzy Kripke models when the underlying complete residuated lattice is linear.

State reduction of fuzzy automata aims to efficiently construct a suitably small fuzzy automaton equivalent to a given one. It is a significant and well-studied problem in automata theory due to its practical applications in various fields. If we relax the requirement for exact equivalence, then we talk about the approximate state reduction problem, which has gained attention only recently. There are two approaches to approximate state reduction: one seeks approximate equivalence to a specified threshold, while the other aims for exact equivalence for length-bounded words. These two approaches have been considered separately. In this paper, we demonstrate that both approaches, and even their combination, can be achieved by merging indistinguishable states of a fuzzy automaton through the use of sequences of fuzzy relations that we introduce in this paper. We provide characterizations of these sequences, and show that they are closely related to certain approximate simulations for fuzzy automata that emerged in the recent literature. However, their subtle differences significantly affect the process of approximate state reduction. By formally proving this distinction, we generalize some well-known results and offer new insight into approximate state reduction. We discuss how all forms of approximate state reduction can be realized and provide algorithms for calculating the proposed sequences and performing the reductions, along with illustrative examples.

The determinization of fuzzy automata is a well-studied problem in theoretical computer science celebrated for its practical applications. Indeed, in the fields of fuzzy discrete event systems, fault diagnosis, clinical monitoring, decision-making systems, and model checking, when a suitable model of a fuzzy automaton is employed, it is desirable to find its language-equivalent deterministic version because of its computational efficiency. Although many methods have been developed to convert a fuzzy automaton to its language equivalent fuzzy deterministic finite automaton (FDfA), they can be applied only for fuzzy automata defined over specific underlying sets of truth values. For example, recently developed determinization methods employ the concept of maximal factorization, which can be defined only on non-locally finite lattices or the Boolean lattice. In addition, not all such determinization methods result in a minimal FDfA. On the other hand, even though such determinization methods have been developed for fuzzy automata over specific underlying structures, these methods cannot be generalized for fuzzy automata over locally finite lattices. This article focuses on filling this gap and develops a novel method for computing a minimal FDfA for a fuzzy automaton defined over a locally finite and divisible residuated lattice. Our method uses the new concept of a reduction graph that emerges from the strict order relation on the resulting fuzzy states, according to which we can construct all minimal FDfAs equivalent to a given fuzzy automaton.

In this article, we introduce fuzzy minimax nets as a novel tool to compute the greatest fuzzy bisimulation/simulation between two finite fuzzy labeled graphs. Fuzzy labeled graphs are a universal data structure for representing fuzzy systems, such as fuzzy automata, fuzzy labeled transition systems, fuzzy Kripke models, fuzzy social networks, and fuzzy interpretations in description logic. The greatest fuzzy bisimulation between two such systems characterizes the similarity between their states, actors, or individuals. Using fuzzy minimax nets, we design the first algorithms for the mentioned computational problems in the case of using the product t-norm, as well as the first algorithms whose complexity order does not depend on the fuzzy values occurring in the inputs for those problems in the case of using the Łukasiewicz t-norm.

In this article, we define$\lambda$-approximate simulations and bisimulations for fuzzy automata over complete Heyting algebras. The value$\lambda$presents the degree of language similarity or equality between observed fuzzy automata. Algorithms for computing the greatest$\lambda$-approximate simulations and bisimulations are given. We show that$\lambda$-approximate simulations and bisimulations on a fuzzy automaton can be effectively used for factorization of fuzzy automata. We present the algorithm that splits the interval of the degrees of language similarity or equality into subintervals with the same minimal corresponding factor fuzzy automata.