  Simulations and bisimulations are well-established notions in crisp/fuzzy
automata theory and are widely used to compare the behaviors of automata. Their
main drawback is that they compare the behaviors of fuzzy automata in a crisp
manner. Recently, fuzzy simulations and fuzzy bisimulations have been defined
for fuzzy automata as a kind of approximate simulations and approximate
bisimulations that compare the behaviors of fuzzy automata in a fuzzy manner.
However, they still suffer from serious shortcomings. First, they still cannot
correlate all fuzzy automata that are intuitively "more or less" (bi)similar.
Second, the currently known algorithms for computing the greatest fuzzy
simulation or bisimulation between two finite fuzzy automata have an
exponential time complexity when the {\L}ukasiewicz or product structure of
fuzzy values is used. This work deals with these problems, providing
approximations of fuzzy simulations and fuzzy bisimulations. We define such
approximations via a novel notion of decreasing sequences of fuzzy relations
whose infima are, under some conditions, fuzzy simulations (respectively,
bisimulations). We call such a sequence a depth-bounded fuzzy simulation
(respectively, bisimulation), as the $n$th element from the sequence compares
the behaviors of fuzzy automata, but only for words with a length bounded by
$n$. We further provide a logical characterization of the greatest
depth-bounded fuzzy simulation or bisimulation between two fuzzy automata by
proving that it satisfies the corresponding Hennessy-Milner property. Finally,
we provide polynomial-time algorithms for computing the $n$th component of the
greatest depth-bounded fuzzy simulation (respectively, bisimulation) between
two finite fuzzy automata.
