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
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Andova. Process algebra with probabilistic choice. In Formal Methods for Real-Time and Probabilistic Systems, LNCS 1601, pages 111–129, 1999.
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.
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.
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.
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.
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.
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.
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.
R. Milner. Communication and Concurrency. Prentice-Hall International, 1989.
A. Philippou, I. Lee, and O. Sokolsky. Weak bisimulation for probabilistic systems. In Proceedings of CONCUR 2000, LNCS 1877, pages 334–349, 2000.
R. Segala. Modeling and Verification of Randomized Distributed Real-Time Systems. Technical report MIT/LCS/TR-676. PhD thesis, MIT, Dept. of EECS, 1995.
R. Segala and N.A. Lynch. Probabilistic simulations for probabilistic processes. In Proceedings of CONCUR 94, LNCS 836, pages 481–496, 1994.
K. Seidel. Probabilistic communicating processes. Technical Report PRG-102, Ph.D. Thesis, Programming Research Group, Oxford University Computing Laboratory, 1992.
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.
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.
W. Yi and K.G. Larsen. Testing probabilistic and nondeterministic processes. In Protocol Specification, Testing and Verification XII, pages 47–61, 1992.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights 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