Skip to main content
SpringerLink
Log in

Axiomatizations for Probabilistic Bisimulation

  • Conference paper
  • First Online:
Automata, Languages and Programming (ICALP 2001)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 2076))

Included in the following conference series:

Abstract

We study complete axiomatizations for different notions of probabilistic bisimulation on a recursion free process algebra with probability and nondeterminism under alternating and non-alternating semantics. The axioms that do not involve probability coincide with the original axioms of Milner. The axioms that involve probability differ depending on the bisimulation under examination and on the semantics that is used, thus revealing the implications of the different choices.

Supported by MURST project TOSCA

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. S. Andova. Process algebra with probabilistic choice. In Formal Methods for Real-Time and Probabilistic Systems, LNCS 1601, pages 111–129, 1999.

    Chapter  Google Scholar 

  2. J.C.M. Baeten, J.A. Bergstra, and S.A. Smolka. Axiomatizing probabilistic processes: ACP with generative probabilities. Information and Computation, 122:234–255, 1995.

    Article  MathSciNet  Google Scholar 

  3. M. Bernardo, L. Donatiello, and R. Gorrieri. Modeling and analyzing concurrent systems with MPA. In Proceedings of the Second Workshop on Process Algebras and Performance Modelling (PAPM), Erlangen, Germany, pages 175–189, 1994.

    Google Scholar 

  4. A. Giacalone, C.C Jou, and S.A. Smolka. Algebraic reasoning for probabilistic concurrent systems. In Proceedings of the Working Conference on Programming Concepts and Methods (IFIP TC2), Sea of Galilee, Israel, 1990.

    Google Scholar 

  5. R.J. van Glabbeek, S.A. Smolka, and B. Steffen. Reactive, generative, and stratified models of probabilistic processes. Information and Computation, 121(1):59–80, 1996.

    Article  Google Scholar 

  6. H. Hansson and B. Jonsson. A framework for reasoning about time and reliability. In Proceedings of the 10th IEEE Symposium on Real-Time Systems, 1989.

    Google Scholar 

  7. C.C. Jou and S.A. Smolka. Equivalences, congruences, and complete axiomatizations for probabilistic processes. In J.Proceedings of CONCUR 90, LNCS 458, pages 367–383, 1990.

    Google Scholar 

  8. K.G. Larsen and A. Skou. Bisimulation through probabilistic testing. In Conference Record of the 16 th ACM Symposium on Principles of Programming Languages, pages 344–352, 1989.

    Google Scholar 

  9. R. Milner. Communication and Concurrency. Prentice-Hall International, 1989.

    Google Scholar 

  10. A. Philippou, I. Lee, and O. Sokolsky. Weak bisimulation for probabilistic systems. In Proceedings of CONCUR 2000, LNCS 1877, pages 334–349, 2000.

    Chapter  Google Scholar 

  11. R. Segala. Modeling and Verification of Randomized Distributed Real-Time Systems. Technical report MIT/LCS/TR-676. PhD thesis, MIT, Dept. of EECS, 1995.

    Google Scholar 

  12. R. Segala and N.A. Lynch. Probabilistic simulations for probabilistic processes. In Proceedings of CONCUR 94, LNCS 836, pages 481–496, 1994.

    Chapter  Google Scholar 

  13. K. Seidel. Probabilistic communicating processes. Technical Report PRG-102, Ph.D. Thesis, Programming Research Group, Oxford University Computing Laboratory, 1992.

    Google Scholar 

  14. E.W. Stark and S.A. Smolka. A complete axiom system for finite-state probabilistic processes. In Proof, Language and Interaction: Essays in Honour of Robin Milner. MIT Press, 1999.

    Google Scholar 

  15. M.Y. Vardi. Automatic verification of probabilistic concurrent finite-state programs. In Proceedings of 26th IEEE Symposium on Foundations of Computer Science, pages 327–338, 1985.

    Google Scholar 

  16. W. Yi and K.G. Larsen. Testing probabilistic and nondeterministic processes. In Protocol Specification, Testing and Verification XII, pages 47–61, 1992.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Università di Bologna, Italy

    Emanuele Bandini & Roberto Segala

Authors
  1. Emanuele Bandini
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Roberto Segala
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Departament de Llenguatges i Sistemes Informátics, Univ. Politècnica de Catalunya, C/Jordi Girona Salgado 1-3, 08034, Barcelona, Spain

    Fernando Orejas

  2. Computer Technology Institute (CTI), University of Patras, 61 Riga Feraiou street, 26221, Patras, Greece

    Paul G. Spirakis

  3. Institute of Information and Computing Sciences, Utrecht University, Padualaan 14, 3584, CH, Utrecht, The Netherlands

    Jan van Leeuwen

Rights and permissions

Reprints and permissions

Copyright information

© 2001 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Bandini, E., Segala, R. (2001). Axiomatizations for Probabilistic Bisimulation. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds) Automata, Languages and Programming. ICALP 2001. Lecture Notes in Computer Science, vol 2076. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48224-5_31

Download citation

  • DOI: https://doi.org/10.1007/3-540-48224-5_31

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-42287-7

  • Online ISBN: 978-3-540-48224-6

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation