Linear distances between Markov chains

Daca, Przemyslaw and Henzinger, Thomas A and Kretinsky, Jan and Petrov, Tatjana (2016) Linear distances between Markov chains. In: CONCUR: Concurrency Theory, August 23-26, 2016, Quebec City, Canada.

[img] Text
LIPIcs-CONCUR-2016-20.pdf - Published Version
Available under License Creative Commons Attribution.
[IST-2017-794-v1+1]
Download (490Kb)
Official URL: http://dx.doi.org/10.4230/LIPIcs.CONCUR.2016.20

Abstract

We introduce a general class of distances (metrics) between Markov chains, which are based on linear behaviour. This class encompasses distances given topologically (such as the total variation distance or trace distance) as well as by temporal logics or automata. We investigate which of the distances can be approximated by observing the systems, i.e. by black-box testing or simulation, and we provide both negative and positive results.

Item Type: Conference or Workshop Item (Paper)
Uncontrolled Keywords: Verification; temporal logic;pprobabilistic systems; statistical model checking; behavioural equivalence
Subjects: 000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems > 004 Data processing & computer science
Research Group: Henzinger Group
SWORD Depositor: Sword Import User
Depositing User: Sword Import User
Date Deposited: 16 Mar 2017 08:02
Last Modified: 30 Aug 2017 14:41
URI: https://repository.ist.ac.at/id/eprint/794

Actions (login required)

View Item View Item