Metrics for weighted transition systems: Axiomatization and complexity

Abstract : Simulation distances are essentially an approximation of simulation which provide a measure of the extent by which behaviors in systems are inequivalent. In this paper, we consider the general quantitative model of weighted transition systems, where transitions are labeled with elements of a finite metric space. We study the so-called point-wise and accumulating simulation distances which provide extensions to the well-known Boolean notion of simulation on labeled transition systems. We introduce weighted process algebras for finite and regular behavior and offer sound and (approximate) complete inference systems for the proposed simulation distances. We also settle the algorithmic complexity of computing the simulation distances.
Type de document :
Article dans une revue
Journal of Theoretical Computer Science (TCS), Elsevier, 2011, 412, pp.3358 - 3369. 〈10.1016/j.tcs.2011.04.003〉
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01088055
Contributeur : Uli Fahrenberg <>
Soumis le : jeudi 27 novembre 2014 - 11:48:08
Dernière modification le : mardi 16 janvier 2018 - 15:54:23
Document(s) archivé(s) le : lundi 2 mars 2015 - 09:22:54

Fichier

tcs.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Kim Guldstrand Larsen, Uli Fahrenberg, Claus Thrane. Metrics for weighted transition systems: Axiomatization and complexity. Journal of Theoretical Computer Science (TCS), Elsevier, 2011, 412, pp.3358 - 3369. 〈10.1016/j.tcs.2011.04.003〉. 〈hal-01088055〉

Partager

Métriques

Consultations de la notice

309

Téléchargements de fichiers

56