  Fuzzy transition systems offer a robust framework for modeling and analyzing
systems with inherent uncertainties and imprecision, which are prevalent in
real-world scenarios. As their extension, nondeterministic fuzzy transition
systems (NFTSs) have been studied in a considerable number of works. Wu et al.
(2018) provided an algorithm for computing the greatest crisp bisimulation of a
finite NFTS $\mathcal{S} = \langle S, A, \delta \rangle$, with a time
complexity of order $O(|S|^4 \cdot |\delta|^2)$ under the assumption that
$|\delta| \geq |S|$. Qiao {\em et al.} (2023) provided an algorithm for
computing the greatest fuzzy bisimulation of a finite NFTS $\mathcal{S}$ under
the G\"odel semantics, with a time complexity of order $O(|S|^4 \cdot
|\delta|^2 \cdot l)$ under the assumption that $|\delta| \geq |S|$, where $l$
is the number of fuzzy values used in $\mathcal{S}$ plus 1. In this work, we
provide efficient algorithms for computing the partition corresponding to the
greatest crisp bisimulation of a finite NFTS $\mathcal{S}$, as well as the
compact fuzzy partition corresponding to the greatest fuzzy bisimulation of
$\mathcal{S}$ under the G\"odel semantics. Their time complexities are of the
order $O((size(\delta) \log{l} + |S|) \log{(|S| + |\delta|)})$, where $l$ is
the number of fuzzy values used in $\mathcal{S}$ plus 2. When $|\delta| \geq
|S|$, this order is within $O(|S| \cdot |\delta| \cdot \log^2{|\delta|})$. The
reduction of time complexity from $O(|S|^4 \cdot |\delta|^2)$ and $O(|S|^4
\cdot |\delta|^2 \cdot l)$ to $O(|S| \cdot |\delta| \cdot \log^2{|\delta|})$ is
a significant contribution of this work. In addition, we introduce
nondeterministic fuzzy labeled transition systems, which extend NFTSs with
fuzzy state labels, and we define and provide results on simulations and
bisimulations between them.
