Characterising Testing Preorders for Finite Probabilistic ProcessesArticle
Authors: Yuxin Deng ; Matthew Hennessy ; Rob van Glabbeek ; Carroll Morgan
0000-0003-0753-418x##NULL##NULL##NULL
Yuxin Deng;Matthew Hennessy;Rob van Glabbeek;Carroll Morgan
In 1992 Wang & Larsen extended the may- and must preorders of De Nicola and
Hennessy to processes featuring probabilistic as well as nondeterministic
choice. They concluded with two problems that have remained open throughout the
years, namely to find complete axiomatisations and alternative
characterisations for these preorders. This paper solves both problems for
finite processes with silent moves. It characterises the may preorder in terms
of simulation, and the must preorder in terms of failure simulation. It also
gives a characterisation of both preorders using a modal logic. Finally it
axiomatises both preorders over a probabilistic version of CSP.
Ruggero Lanotte;Simone Tini, 2021, A weak semantic approach to bisimulation metrics in models with nondeterminism and continuous state spaces, Theoretical Computer Science, 869, pp. 29-61, 10.1016/j.tcs.2020.12.045.
Valentina Castiglioni;Simone Tini, 2020, Raiders of the lost equivalence: Probabilistic branching bisimilarity, Information Processing Letters, 159-160, pp. 105947, 10.1016/j.ipl.2020.105947.
Marcus Gerhold;Arnd Hartmanns;Mariëlle Stoelinga, Lecture notes in computer science, Model-Based Testing for General Stochastic Time, pp. 203-219, 2018, 10.1007/978-3-319-77935-5_15.
Ruggero Lanotte;Simone Tini, Lecture notes in computer science, Weak Bisimulation Metrics in Models with Nondeterminism and Continuous State Spaces, pp. 292-312, 2018, 10.1007/978-3-030-02508-3_16.
Valentina Castiglioni, 2018, Trace and Testing Metrics on Nondeterministic Probabilistic Processes, arXiv (Cornell University), 276, pp. 19-36, 10.4204/eptcs.276.4.
Marcus Gerhold;Mariëlle Stoelinga, Lecture notes in computer science, Model-Based Testing of Probabilistic Systems with Stochastic Time, pp. 77-97, 2017, 10.1007/978-3-319-61467-0_5.
Marcus Gerhold;Mariëlle Stoelinga, Proceedings of the 7th International Workshop on Automating Test Case Design, Selection, and Evaluation, Model-based testing of stochastic systems with IOCO theory, 17, pp. 45-51, 2016, Seattle WA USA, 10.1145/2994291.2994298.
Marcus Gerhold;Mariëlle Stoelinga, Lecture notes in computer science, Model-Based Testing of Probabilistic Systems, pp. 251-268, 2016, 10.1007/978-3-662-49665-7_15.
Marco Bernardo;Davide Sangiorgi;Valeria Vignudelli, On the Discriminating Power of Testing Equivalences for Reactive Probabilistic Systems: Results and Open Problems, pp. 281-296, 2014, 10.1007/978-3-319-10696-0_23, https://hal.inria.fr/hal-01089484.
Marco Bernardo;Rocco De Nicola;Michele Loreti, 2014, Relating strong behavioral equivalences for processes with nondeterminism and probabilities, Theoretical Computer Science, 546, pp. 63-92, 10.1016/j.tcs.2014.03.001, https://doi.org/10.1016/j.tcs.2014.03.001.
Silvia Crafa;Francesco Ranzato, 2014, Logical Characterizations of Behavioral Relations on Transition Systems of Probability Distributions, Padua Research Archive (University of Padua), 16, 1, pp. 1-24, 10.1145/2641566, http://hdl.handle.net/11577/2961100.
Joost-Pieter Katoen, Lecture notes in computer science, Concurrency Meets Probability: Theory and Practice, pp. 44-45, 2013, 10.1007/978-3-642-40184-8_4.
Marco Bernardo;Rocco De Nicola;Michele Loreti, 2013, The Spectrum of Strong Behavioral Equivalences for Nondeterministic and Probabilistic Processes, arXiv (Cornell University), 117, pp. 81-96, 10.4204/eptcs.117.6.
Riccardo Bresciani;Andrew Butterfield, University of Limerick Institutional Repository (University of Limerick), A UTP Semantics of pGCL as a Homogeneous Relation, pp. 191-205, 2012, 10.1007/978-3-642-30729-4_14, http://hdl.handle.net/10344/2607.
Robert M. Hierons;Manuel Núñez, 2012, Using schedulers to test probabilistic distributed systems, Formal Aspects of Computing, 24, 4-6, pp. 679-699, 10.1007/s00165-012-0244-5.
Wei-zhong Yang;Yu-xin Deng, 2011, On real reward testing, Journal of Shanghai Jiaotong University (Science), 16, 4, pp. 479-484, 10.1007/s12204-011-1176-6.
Yuxin Deng;Rob van Glabbeek;Matthew Hennessy;Carroll Morgan, 2011, Real-Reward Testing for Probabilistic Processes (Extended Abstract), arXiv (Cornell University), 57, pp. 61-73, 10.4204/eptcs.57.5.