Weighted Branching Simulation Distance for Parametric Weighted Kripke Structures

Publikation: Bidrag til bog/antologi/rapport/konference proceedingKonferenceartikel i proceedingForskningpeer review

1 Citation (Scopus)

Resumé

This paper concerns branching simulation for weighted Kripke structures with parametric weights. Concretely, we consider a weighted extension of branching simulation where a single transitions can be matched by a sequence of transitions while preserving the branching behavior. We relax this notion to allow for a small degree of deviation in the matching of weights, inducing a directed distance on states. The distance between two states can be used directly to relate properties of the states within a sub-fragment of weighted CTL. The problem of relating systems thus changes to minimizing the distance which, in the general parametric case, corresponds to finding suitable parameter valuations such that one system can approximately simulate another. Although the distance considers a potentially infinite set of transition sequences we demonstrate that there exists an upper bound on the length of relevant sequences, thereby establishing the computability of the distance.
OriginalsprogEngelsk
TitelProceedings Cassting Workshop on Games for the Synthesis of Complex Systems and 3rd International Workshop on Synthesis of Complex Parameters (Cassting'16/SynCoP'16)
Antal sider13
Publikationsdato2016
Sider63-75
DOI
StatusUdgivet - 2016
Begivenhed3rd International Workshop on Synthesis of Complex Parameters - Eindhoven University of Technology, Eindhoven, Holland
Varighed: 3 apr. 20163 apr. 2016
https://lipn.univ-paris13.fr/SynCoP2016/index.php

Workshop

Workshop3rd International Workshop on Synthesis of Complex Parameters
Lokation Eindhoven University of Technology
LandHolland
ByEindhoven
Periode03/04/201603/04/2016
Internetadresse
NavnElectronic Proceedings in Theoretical Computer Science
ISSN2075-2180

Citer dette

Foshammer, L., Larsen, K. G., & Mariegaard, A. (2016). Weighted Branching Simulation Distance for Parametric Weighted Kripke Structures. I Proceedings Cassting Workshop on Games for the Synthesis of Complex Systems and 3rd International Workshop on Synthesis of Complex Parameters (Cassting'16/SynCoP'16) (s. 63-75). Electronic Proceedings in Theoretical Computer Science https://doi.org/10.4204/EPTCS.220.6
Foshammer, Louise ; Larsen, Kim Guldstrand ; Mariegaard, Anders. / Weighted Branching Simulation Distance for Parametric Weighted Kripke Structures. Proceedings Cassting Workshop on Games for the Synthesis of Complex Systems and 3rd International Workshop on Synthesis of Complex Parameters (Cassting'16/SynCoP'16). 2016. s. 63-75 (Electronic Proceedings in Theoretical Computer Science).
@inproceedings{1642786581954edc9c84f21f29ae718d,
title = "Weighted Branching Simulation Distance for Parametric Weighted Kripke Structures",
abstract = "This paper concerns branching simulation for weighted Kripke structures with parametric weights. Concretely, we consider a weighted extension of branching simulation where a single transitions can be matched by a sequence of transitions while preserving the branching behavior. We relax this notion to allow for a small degree of deviation in the matching of weights, inducing a directed distance on states. The distance between two states can be used directly to relate properties of the states within a sub-fragment of weighted CTL. The problem of relating systems thus changes to minimizing the distance which, in the general parametric case, corresponds to finding suitable parameter valuations such that one system can approximately simulate another. Although the distance considers a potentially infinite set of transition sequences we demonstrate that there exists an upper bound on the length of relevant sequences, thereby establishing the computability of the distance.",
keywords = "branching simulation, simulation distance, parametric weighted kripke structure",
author = "Louise Foshammer and Larsen, {Kim Guldstrand} and Anders Mariegaard",
year = "2016",
doi = "10.4204/EPTCS.220.6",
language = "English",
series = "Electronic Proceedings in Theoretical Computer Science",
publisher = "Open Publishing Association",
pages = "63--75",
booktitle = "Proceedings Cassting Workshop on Games for the Synthesis of Complex Systems and 3rd International Workshop on Synthesis of Complex Parameters (Cassting'16/SynCoP'16)",

}

Foshammer, L, Larsen, KG & Mariegaard, A 2016, Weighted Branching Simulation Distance for Parametric Weighted Kripke Structures. i Proceedings Cassting Workshop on Games for the Synthesis of Complex Systems and 3rd International Workshop on Synthesis of Complex Parameters (Cassting'16/SynCoP'16). Electronic Proceedings in Theoretical Computer Science, s. 63-75, Eindhoven, Holland, 03/04/2016. https://doi.org/10.4204/EPTCS.220.6

Weighted Branching Simulation Distance for Parametric Weighted Kripke Structures. / Foshammer, Louise; Larsen, Kim Guldstrand; Mariegaard, Anders.

Proceedings Cassting Workshop on Games for the Synthesis of Complex Systems and 3rd International Workshop on Synthesis of Complex Parameters (Cassting'16/SynCoP'16). 2016. s. 63-75 (Electronic Proceedings in Theoretical Computer Science).

Publikation: Bidrag til bog/antologi/rapport/konference proceedingKonferenceartikel i proceedingForskningpeer review

TY - GEN

T1 - Weighted Branching Simulation Distance for Parametric Weighted Kripke Structures

AU - Foshammer, Louise

AU - Larsen, Kim Guldstrand

AU - Mariegaard, Anders

PY - 2016

Y1 - 2016

N2 - This paper concerns branching simulation for weighted Kripke structures with parametric weights. Concretely, we consider a weighted extension of branching simulation where a single transitions can be matched by a sequence of transitions while preserving the branching behavior. We relax this notion to allow for a small degree of deviation in the matching of weights, inducing a directed distance on states. The distance between two states can be used directly to relate properties of the states within a sub-fragment of weighted CTL. The problem of relating systems thus changes to minimizing the distance which, in the general parametric case, corresponds to finding suitable parameter valuations such that one system can approximately simulate another. Although the distance considers a potentially infinite set of transition sequences we demonstrate that there exists an upper bound on the length of relevant sequences, thereby establishing the computability of the distance.

AB - This paper concerns branching simulation for weighted Kripke structures with parametric weights. Concretely, we consider a weighted extension of branching simulation where a single transitions can be matched by a sequence of transitions while preserving the branching behavior. We relax this notion to allow for a small degree of deviation in the matching of weights, inducing a directed distance on states. The distance between two states can be used directly to relate properties of the states within a sub-fragment of weighted CTL. The problem of relating systems thus changes to minimizing the distance which, in the general parametric case, corresponds to finding suitable parameter valuations such that one system can approximately simulate another. Although the distance considers a potentially infinite set of transition sequences we demonstrate that there exists an upper bound on the length of relevant sequences, thereby establishing the computability of the distance.

KW - branching simulation

KW - simulation distance

KW - parametric weighted kripke structure

U2 - 10.4204/EPTCS.220.6

DO - 10.4204/EPTCS.220.6

M3 - Article in proceeding

T3 - Electronic Proceedings in Theoretical Computer Science

SP - 63

EP - 75

BT - Proceedings Cassting Workshop on Games for the Synthesis of Complex Systems and 3rd International Workshop on Synthesis of Complex Parameters (Cassting'16/SynCoP'16)

ER -

Foshammer L, Larsen KG, Mariegaard A. Weighted Branching Simulation Distance for Parametric Weighted Kripke Structures. I Proceedings Cassting Workshop on Games for the Synthesis of Complex Systems and 3rd International Workshop on Synthesis of Complex Parameters (Cassting'16/SynCoP'16). 2016. s. 63-75. (Electronic Proceedings in Theoretical Computer Science). https://doi.org/10.4204/EPTCS.220.6