Faella, Marco (2009) Linear and Branching System Metrics. [Pubblicazione in rivista scientifica]

Il contenuto (Full text) non è disponibile all'interno di questo archivio.
Tipologia del documento: Pubblicazione in rivista scientifica
Lingua: English
Titolo: Linear and Branching System Metrics
Autori:
AutoreEmail
Faella, Marco[non definito]
Autore/i: L. de Alfaro, M. Faella, M. Stoelinga
Data: 2009
Numero di pagine: 15
Dipartimento: Scienze fisiche
Titolo del periodico: IEEE TRANSACTIONS ON SOFTWARE ENGINEERING
Data: 2009
Volume: 35
Numero: 2
Intervallo di pagine: pp. 258-273
Numero di pagine: 15
Parole chiave: simulation, metrics
Depositato il: 21 Ott 2010 06:57
Ultima modifica: 30 Apr 2014 19:43
URI: http://www.fedoa.unina.it/id/eprint/7605

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.

Actions (login required)

Modifica documento Modifica documento