Trace and Testing Metrics on Nondeterministic Probabilistic Processes

Valentina Castiglioni
(INRIA Saclay - Ile de France)

The combination of nondeterminism and probability in concurrent systems lead to the development of several interpretations of process behavior. If we restrict our attention to linear properties only, we can identify three main approaches to trace and testing semantics: the trace distributions, the trace-by-trace and the extremal probabilities approaches. In this paper, we propose novel notions of behavioral metrics that are based on the three classic approaches above, and that can be used to measure the disparities in the linear behavior of processes wrt trace and testing semantics. We study the properties of these metrics, like non-expansiveness, and we compare their expressive powers.

In Jorge A. Pérez and Simone Tini: Proceedings Combined 25th International Workshop on Expressiveness in Concurrency and 15th Workshop on Structural Operational Semantics (EXPRESS/SOS 2018), Beijing, China, September 3, 2018, Electronic Proceedings in Theoretical Computer Science 276, pp. 19–36.
Published: 24th August 2018.

ArXived at: http://dx.doi.org/10.4204/EPTCS.276.4 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org