On the Efficiency of Deciding Probabilistic Automata Weak Bisimulation

Abstract

Weak probabilistic bisimulation on probabilistic automata can be decided by an algorithm that needs to check a polynomial number of linear programming problems encoding weak transitions. It is hence polynomial, but not guaranteed to be strongly polynomial. In this paper we show that for polynomial rational proba- bilistic automata strong polynomial complexity can be ensured. We further discuss complexity bounds for generic probabilistic automata. Then we consider several practical algorithms and LP transformations that enable an efficient solution for the concrete weak transition problem. This sets the ground for effective compositional minimisation approaches for probabilistic automata and Markov decision processes.