  Behaviour distances to measure the resemblance of two states in a
(nondeterministic) fuzzy transition system have been proposed recently in the
literature. Such a distance, defined as a pseudo-ultrametric over the state
space of the model, provides a quantitative analogue of bisimilarity. In this
paper, we focus on the problem of computing these distances. We first extend
the definition of the pseudo-ultrametric by introducing discount such that the
discounting factor being equal to 1 captures the original definition. We then
provide polynomial-time algorithms to calculate the behavioural distances, in
both the non-discounted and the discounted setting. The algorithm is strongly
polynomial in the former case. Furthermore, we give a polynomial-time algorithm
to compute bisimulation over fuzzy transition systems which captures the
distance being equal to 0.
