Linear distances between Markov chains Conference Paper


Author(s): Daca, Przemyslaw; Henzinger, Thomas A; Křetínský, Jan; Petrov, Tatjana
Title: Linear distances between Markov chains
Title Series: LIPIcs
Affiliation IST Austria
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.
Keywords: verification; Temporal logic; Probabilistic systems; Statistical model checking; behavioural equivalence
Conference Title: CONCUR: Concurrency Theory
Volume: 59
Conference Dates: August 23-26, 2016
Conference Location: Québec City, Canada
ISBN: 978-3-95977-017-0
Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik  
Date Published: 2016-01-01
Start Page: 20:1
End Page: 20:15
Copyright Statement: CC BY
URL:
DOI: 10.4230/LIPIcs.CONCUR.2016.20
Notes: This research was funded in part by the European Research Council (ERC) under grant agreement 267989 (QUAREM), the Austrian Science Fund (FWF) under grants project S11402-N23 (RiSE and SHiNE) and Z211-N23 (Wittgenstein Award), by the Czech Science Foundation Grant No. P202/12/G061, and by the SNSF Advanced Postdoc. Mobility Fellowship – grant number P300P2_161067.
Open access: yes (OA journal)
IST Austria Authors
  1. Thomas A. Henzinger
    415 Henzinger
  2. Przemysław, Daca
    12 Daca
  3. Tatjana Petrov
    12 Petrov
Related IST Austria Work