Linear and Branching System Metrics

FAELLA, MARCO (2009) Linear and Branching System Metrics. [Pubblicazione su rivista scientifica]

Full text non disponibile da questo archivio.

Abstract

We extend the classical system relations of trace inclusion, trace equivalence, simulation, and bisimulation to a quantitative setting in which propositions are interpreted not as boolean values, but as elements of arbitrary metric spaces. Trace inclusion and equivalence give rise to asymmetrical and symmetrical linear distances, while simulation and bisimulation give rise to asymmetrical and symmetrical branching distances. We study the relationships among these distances, and we provide a full logical characterization of the distances in terms of quantitative versions of LTL and mu-calculus. We show that, while trace inclusion (resp. equivalence) coincides with simulation (resp. bisimulation) for deterministic boolean transition systems, linear and branching distances do not coincide for deterministic metric transition systems. Finally, we provide algorithms for computing the distances over finite systems, together with a matching lower complexity bound.

Tipologia di documento:Pubblicazione su rivista scientifica
Parole chiave:simulation, metrics
Settori scientifico-disciplinari MIUR:Non specificato
Stato del full text:Accessibilità ristretta
Data:2009
Altri Autori:L. de Alfaro, M. Faella, M. Stoelinga
Numero di pagine:15
Intervallo di pagina:pp. 258-273
Volume:35
Numero:2
Dipartimento o Struttura:Dipartimento di Scienze Fisiche
Titolo rivista/pubblicazione:IEEE TRANSACTIONS ON SOFTWARE ENGINEERING
Numero di sistema:7605
Depositato il:21 Ottobre 2010 08:57
Ultima modifica:21 Ottobre 2010 08:57

Solo per gli Amministratori dell'archivio: edita il record