Linear-Time and May-Testing in a Probabilistic Reactive Setting

Abstract : We consider reactive probabilistic labelled transition systems (rplts), a model where internal choices are refined by probabilistic choices. In this setting, we study the relationship between linear-time and may-testing semantics, where an angelic view of nondeterminism is taken. Building on the model of d-trees of Cleaveland et al., we first introduce a clean model of probabilistic may-testing, based on simple concepts from measure theory. In particular, we define a probability space where statements of the form “p may pass test o” naturally correspond to measurable events. We then obtain an observer-independent characterization of the may-testing preorder, based on comparing the probability of sets of traces, rather than of individual traces. This entails that may-testing is strictly finer than linear-time semantics. Next, we characterize the may-testing preorder in terms of the probability of satisfying safety properties, expressed as languages of infinite trees rather than traces. We then identify a significative subclass of rplts where linear and may-testing semantics do coincide: these are the separated rplts, where actions are partitioned into probabilistic and nondeterministic ones, and at each state only one type is available.
Type de document :
Communication dans un congrès
Roberto Bruni; Juergen Dingel. 13th Conference on Formal Methods for Open Object-Based Distributed Systems (FMOODS) / 31th International Conference on FORmal TEchniques for Networked and Distributed Systems (FORTE), Jun 2011, Reykjavik,, Iceland. Springer, Lecture Notes in Computer Science, LNCS-6722, pp.29-43, 2011, Formal Techniques for Distributed Systems. 〈10.1007/978-3-642-21461-5_2〉
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01583326
Contributeur : Hal Ifip <>
Soumis le : jeudi 7 septembre 2017 - 11:10:26
Dernière modification le : lundi 11 septembre 2017 - 10:46:59

Fichier

978-3-642-21461-5_2_Chapter.pd...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Lucia Acciai, Michele Boreale, Rocco Nicola. Linear-Time and May-Testing in a Probabilistic Reactive Setting. Roberto Bruni; Juergen Dingel. 13th Conference on Formal Methods for Open Object-Based Distributed Systems (FMOODS) / 31th International Conference on FORmal TEchniques for Networked and Distributed Systems (FORTE), Jun 2011, Reykjavik,, Iceland. Springer, Lecture Notes in Computer Science, LNCS-6722, pp.29-43, 2011, Formal Techniques for Distributed Systems. 〈10.1007/978-3-642-21461-5_2〉. 〈hal-01583326〉

Partager

Métriques

Consultations de la notice

33

Téléchargements de fichiers

11