Submitted: July 2013
Abstract
Turrini and Hermanns recently showed that weak bisimulation on probabilistic automata is decidable in polynomial time. That makes the algorithm at least theoretically efficient and raises the question of its applicability. This thesis gives a first implementation of this algorithm written in Java. Based on that, it evaluates the efficiency and applicability of it as well as the effectivity of the algorithm with respect to automaton minimization. While the results still give cause of concern regarding the runtime of the algorithm which limits the practical usability of the algorithm for now, the effectivity of weak bisimulation motivates further investigation in this area.