TY - GEN
T1 - Linear distances between Markov chains
AU - Daca, Przemysław
AU - Henzinger, Thomas A.
AU - Křetínský, Jan
AU - Petrov, Tatjana
N1 - Publisher Copyright:
© Przemysław Daca, Thomas A. Henzinger, Jan Kretínský, and Tatjana Petrov; licensed under Creative Commons License CC-BY.
PY - 2016/8/1
Y1 - 2016/8/1
N2 - 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.
AB - 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.
KW - Behavioural equivalence
KW - Probabilistic systems
KW - Statistical model checking
KW - Temporal logic
KW - Verification
UR - http://www.scopus.com/inward/record.url?scp=85012898478&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.CONCUR.2016.20
DO - 10.4230/LIPIcs.CONCUR.2016.20
M3 - Conference contribution
AN - SCOPUS:85012898478
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 27th International Conference on Concurrency Theory, CONCUR 2016
A2 - Desharnais, Josee
A2 - Jagadeesan, Radha
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 27th International Conference on Concurrency Theory, CONCUR 2016
Y2 - 23 August 2016 through 26 August 2016
ER -