Weighted Branching Simulation Distance for Parametric Weighted Kripke Structures
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 t...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Open Publishing Association
2016-07-01
|
| Series: | Electronic Proceedings in Theoretical Computer Science |
| Online Access: | http://arxiv.org/pdf/1608.00657v1 |
| _version_ | 1819260388827463680 |
|---|---|
| author | Louise Foshammer Kim Guldstrand Larsen Anders Mariegaard |
| author_facet | Louise Foshammer Kim Guldstrand Larsen Anders Mariegaard |
| author_sort | Louise Foshammer |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-23T19:25:07Z |
| format | Article |
| id | doaj.art-785225bc576649d09ff7ee129e07be7f |
| institution | Directory Open Access Journal |
| issn | 2075-2180 |
| language | English |
| last_indexed | 2024-12-23T19:25:07Z |
| publishDate | 2016-07-01 |
| publisher | Open Publishing Association |
| record_format | Article |
| series | Electronic Proceedings in Theoretical Computer Science |
| spelling | doaj.art-785225bc576649d09ff7ee129e07be7f2022-12-21T17:34:04ZengOpen Publishing AssociationElectronic Proceedings in Theoretical Computer Science2075-21802016-07-01220Proc. Cassting 2016/SynCoP'16637510.4204/EPTCS.220.6:22Weighted Branching Simulation Distance for Parametric Weighted Kripke StructuresLouise Foshammer0Kim Guldstrand Larsen1Anders Mariegaard2 Aalborg University Aalborg University Aalborg University 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.http://arxiv.org/pdf/1608.00657v1 |
| spellingShingle | Louise Foshammer Kim Guldstrand Larsen Anders Mariegaard Weighted Branching Simulation Distance for Parametric Weighted Kripke Structures Electronic Proceedings in Theoretical Computer Science |
| title | Weighted Branching Simulation Distance for Parametric Weighted Kripke Structures |
| title_full | Weighted Branching Simulation Distance for Parametric Weighted Kripke Structures |
| title_fullStr | Weighted Branching Simulation Distance for Parametric Weighted Kripke Structures |
| title_full_unstemmed | Weighted Branching Simulation Distance for Parametric Weighted Kripke Structures |
| title_short | Weighted Branching Simulation Distance for Parametric Weighted Kripke Structures |
| title_sort | weighted branching simulation distance for parametric weighted kripke structures |
| url | http://arxiv.org/pdf/1608.00657v1 |
| work_keys_str_mv | AT louisefoshammer weightedbranchingsimulationdistanceforparametricweightedkripkestructures AT kimguldstrandlarsen weightedbranchingsimulationdistanceforparametricweightedkripkestructures AT andersmariegaard weightedbranchingsimulationdistanceforparametricweightedkripkestructures |