Trustworthy Systems

Remarks on testing probabilistic processes

Authors

Yuxin Deng, Rob van Glabbeek, Matthew Hennessy, Carroll Morgan and Cuicui Zhang

UNSW

NICTA

University of Sussex

Abstract

We develop a general testing scenario for probabilistic processes, giving rise to two theories: probabilistic may testing and probabilistic must testing. These are applied to a simple probabilistic version of the process calculus CSP. We examine the algebraic theory of probabilistic testing, and show that many of the axioms of standard testing are no longer valid in our probabilistic setting; even for non-probabilistic CSP processes, the distinguishing power of probabilistic tests is much greater than that of standard tests. We develop a method for deriving inequations valid in probabilistic may testing based on a probabilistic extension of the notion of simulation. Using this, we obtain a complete axiomatisation for non-probabilistic processes subject to probabilistic may testing.

BibTeX Entry

  @article{Deng_GHMZ_07,
    author           = {Deng, Yuxin and van Glabbeek, Robert and Hennessy, Matthew and Morgan, Carroll and Zhang, Cuicui},
    issn             = {1571-0661},
    journal          = {Electronic Notes in Theoretical Computer Science},
    keywords         = {probabilistic processes, nondeterminism, csp, transition systems, testing equivalences, simulation,
                        complete axiomatisations, structural operational semantics.},
    month            = apr,
    number           = { },
    pages            = {359--397},
    paperurl         = {https://trustworthy.systems/publications/nicta_full_text/145.pdf},
    title            = {Remarks on Testing Probabilistic Processes},
    volume           = {172},
    year             = {2007}
  }

Download