Congruences and Bisimulations for Continuous-Time Stochastic Logic

  • Ernst-Erich Doberkat
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3722)


Continuous stochastic logic (CSL) deals with the verification of systems operating in continuous time, it may be traced to the well known tree logic CTL. We propose a probabilistic interpretation of this logic that is based on stochastic relations without making specific assumptions on the underlying distribution, and study the problem of bisimulations in a fairly general context from the viewpoint of congruences for stochastic relations. The goal is finding minimal sets of formulas that permit efficient checking of models.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Baier, C., Haverkort, B., Hermanns, H., Koert, J.-P.: Model-checking algorithms for continuous time Markov chains. IEEE Trans. Softw. Eng. 29(6), 524–541 (2003)CrossRefGoogle Scholar
  2. 2.
    Desharnais, J., Edalat, A., Panangaden, P.: Bisimulation of labelled Markov-processes. Information and Computation 179(2), 163–193 (2002)zbMATHCrossRefMathSciNetGoogle Scholar
  3. 3.
    Desharnais, J., Panangaden, P.: Continuous stochastic logic characterizes bisimulation of continuous-time Markov processes. J. Log. Alg. Programming 56(1-2), 99–115 (2003)zbMATHCrossRefMathSciNetGoogle Scholar
  4. 4.
    Doberkat, E.-E.: Semi-pullbacks and bisimulations in categories of stochastic relations. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 996–1007. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  5. 5.
    Doberkat, E.-E.: Stochastic relations: congruences, bisimulations and the Hennessy-Milner theorem. SIAM J. Computing (2005) (in print)Google Scholar
  6. 6.
    Doberkat, E.-E.: Zeno paths, congruences and bisimulations for continuous-time stochastic logic. Technical Report 155, Chair for Software Technology, University of Dortmund (March 2005)Google Scholar
  7. 7.
    Narasimha, M., Cleaveland, R., Iyer, P.: Probabilistic temporal logics via the modal mu-calculus. In: Thomas, W. (ed.) FOSSACS 1999. LNCS, vol. 1578, pp. 288–305. Springer, Heidelberg (1999)CrossRefGoogle Scholar
  8. 8.
    Srivastava, S.M.: A Course on Borel Sets. Graduate Texts in Mathematics. Springer, Berlin (1998)zbMATHGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Ernst-Erich Doberkat
    • 1
  1. 1.Chair for Software TechnologyUniversity of Dortmund 

Personalised recommendations