tr-announce

Download

tr-announce@lists.rwth-aachen.de

December 2011

1 participants
1 discussions

2011-26: The Complexity of Deciding a Behavioural Pseudometric on Probabilistic Automata
by Thomas Ströder 23 Dec '11

23 Dec '11

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}). -- Thomas Ströder mailto:stroeder@informatik.rwth-aachen.de LuFG Informatik 2 http://verify.rwth-aachen.de/stroeder RWTH Aachen phone: +49 241 80-21241

1 0