Bernardo, Marco and De Nicola, Rocco and Loreti, Michele - Revisiting Trace and Testing Equivalences for Nondeterministic and Probabilistic Processes

lmcs:1137 - Logical Methods in Computer Science, March 3, 2014, Volume 10, Issue 1
Revisiting Trace and Testing Equivalences for Nondeterministic and Probabilistic Processes

Authors: Bernardo, Marco and De Nicola, Rocco and Loreti, Michele

Two of the most studied extensions of trace and testing equivalences to nondeterministic and probabilistic processes induce distinctions that have been questioned and lack properties that are desirable. Probabilistic trace-distribution equivalence differentiates systems that can perform the same set of traces with the same probabilities, and is not a congruence for parallel composition. Probabilistic testing equivalence, which relies only on extremal success probabilities, is backward compatible with testing equivalences for restricted classes of processes, such as fully nondeterministic processes or generative/reactive probabilistic processes, only if specific sets of tests are admitted. In this paper, new versions of probabilistic trace and testing equivalences are presented for the general class of nondeterministic and probabilistic processes. The new trace equivalence is coarser because it compares execution probabilities of single traces instead of entire trace distributions, and turns out to be compositional. The new testing equivalence requires matching all resolutions of nondeterminism on the basis of their success probabilities, rather than comparing only extremal success probabilities, and considers success probabilities in a trace-by-trace fashion, rather than cumulatively on entire resolutions. It is fully backward compatible with testing equivalences for restricted classes of processes; as a consequence, the trace-by-trace approach uniformly captures the standard probabilistic testing equivalences for generative and reactive probabilistic processes. The paper discusses in full details the new equivalences and provides a simple spectrum that relates them with existing ones in the setting of nondeterministic and probabilistic processes.


Source : oai:arXiv.org:1402.5365
DOI : 10.2168/LMCS-10(1:16)2014
Volume: Volume 10, Issue 1
Published on: March 3, 2014
Submitted on: March 4, 2013
Keywords: Computer Science - Logic in Computer Science


Share

Consultation statistics

This page has been seen 77 times.
This article's PDF has been downloaded 21 times.