A complete approximation theory for weighted transition systems

Hansen, Mikkel and Larsen, Kim Guldstrand and Mardare, Radu and Pedersen, Mathias Ruggaard and Xue, Bingtian; Franzle, Martin and Kapur, Deepak and Zhan, Naijun, eds. (2016) A complete approximation theory for weighted transition systems. In: Dependable Software Engineering. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) . Springer-Verlag, CHN, pp. 213-228. ISBN 9783319476766 (https://doi.org/10.1007/978-3-319-47677-3_14)

[thumbnail of Hansen-etal-SETTA2016-A-complete-approximation-theory-weighted-transition-systems]
Preview
 Text. Filename: Hansen_etal_SETTA2016_A_complete_approximation_theory_weighted_transition_systems.pdf
Accepted Author Manuscript
Download (393kB)| Preview

Abstract

We propose a way of reasoning about minimal and maximal values of the weights of transitions in a weighted transition system (WTS). This perspective induces a notion of bisimulation that is coarser than the classic bisimulation: it relates states that exhibit transitions to bisimulation classes with the weights within the same boundaries. We propose a customized modal logic that expresses these numeric boundaries for transition weights by means of particular modalities. We prove that our logic is invariant under the proposed notion of bisimulation. We show that the logic enjoys the finite model property which allows us to prove the decidability of satisfiability and provide an algorithm for satisfiability checking. Last but not least, we identify a complete axiomatization for this logic, thus solving a long-standing open problem in this field. All our results are proven for a class of WTSs without the image-finiteness restriction, a fact that makes this development general and robust.

CORE (COnnecting REpositories)