Roberto Segala and Nancy Lynch. Probabilistic simulations for probabilistic processes. In Bengt Jonsson and Joachim Parrow, editors, 5th International Conference on Concurrency Theory (CONCUR'94, Uppsala, Sweden, August 1994), volume 836 of Lecture Notes in Computer Science, pages 481-496. Springer-Verlag 1994. A revised version is submitted to the Nordic Journal of Computing for a special issue of selected papers from CONCUR'94. .pdf

Abstract

Several probabilistic simulation relations for probabilistic systems are defined and evaluated according to two criteria: compositionality and preservation of ``interesting'' properties. Here, the interesting properties of a system are identified with those that are expressible in an untimed version of the Timed Probabilistic concurrent Computation Tree Logic (TPCTL) of Hansson. The definitions are made, and the evaluations carried out, in terms of a general labeled transition system model for concurrent probabilistic computation.