Metrics for weighted transition systems: Axiomatization and complexity

Kim Guldstrand Larsen, U. Fahrenberg, C. Thrane

Research output: Contribution to journalJournal articleResearchpeer-review

25 Citations (Scopus)

Abstract

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.
Original languageEnglish
JournalTheoretical Computer Science
Volume412
Issue number28
Pages (from-to)3358-3369
Number of pages12
ISSN0304-3975
DOIs
Publication statusPublished - 1 Jun 2011

Fingerprint

Dive into the research topics of 'Metrics for weighted transition systems: Axiomatization and complexity'. Together they form a unique fingerprint.

Cite this