tr-announce December 2011

tr-announce@lists.rwth-aachen.de

1 participants
1 discussions

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

by Thomas Ströder

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

12 years, 9 months

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

2004

2003

2002

2001

tr-announce December 2011