AIB 2011-26: The Complexity of Deciding a Behavioural Pseudometric on Probabilistic Automata

The following technical report is available from http://aib.informatik.rwth-aachen.de:

The Complexity of Deciding a Behavioural Pseudometric on Probabilistic Automata Hongfei Fu AIB 2011-26

In this paper we study the complexity of computing a behavioural pseudometric on Segala's probabilistic automata. The pseudometric concerned here stems from a real-valued logic (by Desharnais \emph{et al}) and does not discount the future. We show that the problem whether the pseudometric between two states of a finite probabilistic automata is under a given threshold lies in the intersection of NP and coNP. This result significantly improves the previous PSPACE upperbound (by e.g. van Breugel \emph{et al}).