This paper deals with probabilistic and nondeterministic processes represen
ted by a variant of labeled transition systems where any outgoing transitio
n of a state s is augmented with probabilities for the possible successor s
tates. Our main contributions are algorithms for computing this bisimulatio
n equivalence classes as introduced by Larsen and Skou (1996, Inform. ant C
omput. 99, 1-28 ), and the simulation preorder a la Segala and Lynch (1995,
Nordic J. Comput. 2, 250-273). The algorithm for deciding bisimilarity is
based on a variant of the traditional partitioning technique and runs in ti
me O(mn(log m + log n)) where m is the number of transitions and n the numb
er of states. The main idea for computing the simulation preorder is the re
duction to maximum flow problems in suitable networks. Using the method of
Cheriyan, Hagerup, and Mehlhorn, (1990, Lecture Notes in Computer Science,
Vol. 443, pp.235-248, Springer-Verlag, Berlin) for computing the maximum fl
ow, the algorithm runs in time O((mn(6) + m(2)n(3))/log n). Moreover, we sh
ow that the network-based technique is also applicable to compute the simul
ation-like relation of Jonsson and Larsen (1991, "Proc. LICS'91" pp. 266-27
7) in fully probabilistic systems (a variant of ordinary labeled transition
systems where the nondeterminism is totally resolved by probabilistic choi
ces). (C) 2000 Academic Press.