Weak Stochastic Bisimulation for Non-markovian Processes

  • Natalia López
  • Manuel Núñez
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3722)


In this paper we introduce a novel notion of bisimulation to properly capture the behavior of stochastic systems with general distributions. The key idea consists in the identification of different sequences of random variables if the additions of the random variables of each sequence are identically distributed. That is, we will not only identify sequences of internal actions with one of them (as it is usually done in weak bisimulations) but we will also reduce (in some conditions) sequences of stochastic transitions to only one transition. Therefore, we will identify processes that are considered non-equivalent in previous notions of bisimulation for this kind of languages.


Equivalence Class Equivalence Relation Probability Distribution Function Internal Transition Label Transition System 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. [ABC+94]
    Ajmone Marsan, M., Bianco, A., Ciminiera, L., Sisto, R., Valenzano, A.: A LOTOS extension for the performance analysis of distributed systems. IEEE/ACM Transactions on Networking 2(2), 151–165 (1994)CrossRefGoogle Scholar
  2. [BC00]
    Bernardo, M., Cleaveland, W.R.: A theory of testing for markovian processes. In: Palamidessi, C. (ed.) CONCUR 2000. LNCS, vol. 1877, pp. 305–319. Springer, Heidelberg (2000)CrossRefGoogle Scholar
  3. [BG98]
    Bernardo, M., Gorrieri, R.: A tutorial on EMPA: A theory of concurrent processes with nondeterminism, priorities, probabilities and time. Theoretical Computer Science 202, 1–54 (1998)zbMATHCrossRefMathSciNetGoogle Scholar
  4. [BG02]
    Bravetti, M., Gorrieri, R.: The theory of interactive generalized semi-Markov processes. Theoretical Computer Science 282(1), 5–32 (2002)zbMATHCrossRefMathSciNetGoogle Scholar
  5. [BH97]
    Baier, C., Hermanns, H.: Weak bisimulation for fully probabilistic processes. In: Grumberg, O. (ed.) CAV 1997. LNCS, vol. 1254, pp. 119–130. Springer, Heidelberg (1997)Google Scholar
  6. [BW90]
    Baeten, J.C.M., Weijland, W.P.: Process Algebra. Cambridge Tracts in Computer Science 18. Cambridge University Press, Cambridge (1990)CrossRefGoogle Scholar
  7. [DKB98]
    D’Argenio, P.R., Katoen, J.-P., Brinksma, E.: An algebraic approach to the specification of stochastic systems. In: Programming Concepts and Methods, pp. 126–147. Chapman & Hall, Boca Raton (1998)Google Scholar
  8. [GHR93]
    Götz, N., Herzog, U., Rettelbach, M.: Multiprocessor and distributed system design: The integration of functional specification and performance analysis using stochastic process algebras. In: Donatiello, L., Nelson, R. (eds.) SIGMETRICS 1993 and Performance 1993. LNCS, vol. 729, pp. 121–146. Springer, Heidelberg (1993)CrossRefGoogle Scholar
  9. [Hen88]
    Hennessy, M.: Algebraic Theory of Processes. MIT Press, Cambridge (1988)zbMATHGoogle Scholar
  10. [Her98]
    Hermanns, H.: Interactive Markov Chains. PhD thesis, Universität Erlangen-Nürnberg (1998)Google Scholar
  11. [HHK02]
    Hermanns, H., Herzog, U., Katoen, J.-P.: Process algebra for performance evaluation. Theoretical Computer Science 274(1-2), 43–87 (2002)zbMATHCrossRefMathSciNetGoogle Scholar
  12. [Hil96]
    Hillston, J.: A Compositional Approach to Performance Modelling. Cambridge University Press, Cambridge (1996)CrossRefGoogle Scholar
  13. [Hoa85]
    Hoare, C.A.R.: Communicating Sequential Processes. Prentice Hall, Englewood Cliffs (1985)zbMATHGoogle Scholar
  14. [HS00]
    Harrison, P.G., Strulo, B.: SPADES – a process algebra for discrete event simulation. Journal of Logic Computation 10(1), 3–42 (2000)zbMATHCrossRefMathSciNetGoogle Scholar
  15. [LN00]
    López, N., Núñez, M.: NMSPA: A non-markovian model for stochastic processes. In: International Workshop on Distributed System Validation and Verification (DSVV 2000), pp. 33–40 (2000)Google Scholar
  16. [LN01]
    López, N., Núñez, M.: A testing theory for generally distributed stochastic processes. In: Larsen, K.G., Nielsen, M. (eds.) CONCUR 2001. LNCS, vol. 2154, pp. 321–335. Springer, Heidelberg (2001)CrossRefGoogle Scholar
  17. [LNR04]
    López, N., Núñez, M., Rubio, F.: An integrated framework for the analysis of asynchronous communicating stochastic processes. Formal Aspects of Computing 16(3), 238–262 (2004)zbMATHCrossRefGoogle Scholar
  18. [Mil89]
    Milner, R.: Communication and Concurrency. Prentice Hall, Englewood Cliffs (1989)zbMATHGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Natalia López
    • 1
  • Manuel Núñez
    • 1
  1. 1.Dpt. Sistemas Informáticos y ProgramaciónUniversidad Complutense de Madrid 

Personalised recommendations