TY - JOUR
T1 - Metrics for weighted transition systems: Axiomatization and complexity
AU - Larsen, Kim Guldstrand
AU - Fahrenberg, U.
AU - Thrane, C.
PY - 2011/6/1
Y1 - 2011/6/1
N2 - Simulation distances are essentially approximations 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.
AB - Simulation distances are essentially approximations 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.
UR - http://www.scopus.com/inward/record.url?scp=79959727708&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2011.04.003
DO - 10.1016/j.tcs.2011.04.003
M3 - Journal article
AN - SCOPUS:79959727708
SN - 0304-3975
VL - 412
SP - 3358
EP - 3369
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 28
ER -