Abstract
In this paper we define a congruence relation for regular terms of sPBC (stochastic Petri Box Calculus), by means of which we identify those processes that have the same behaviour, not only in terms of the multiactions that they can perform, but also taking into account the stochastic information that they have associated. In order to define this equivalence relation we have to define an adequate semantics for the synchronization operator, as well as a new labelled transition system for regular terms of sPBC.
Similar content being viewed by others
References
Ajmone Marsan M, Balbo G, Conte G, Donatelli S, Franceschinis G (1995) Modelling with generalized stochastic Petri nets. Wiley, New York
Baeten JCM (1992) The total order assumption In: Best E. (ed) Proceedings of the workshop “What good is partial order”, Sheffiel Hildesheimer Informatik-Berichte 13/92, Universitat Hildesheim, pp 1–11
Bernando M, Gorrieri R (1998) A tutorial on EMPA: a theory of concurrent processes with nondeterminism, priorities, probabilities and time. Theor Comput Sci 202(1–2):1–54
Best E, Devillers R, Koutny M (1998) Petri nets, process algebras and programming languages. In: Reisig W, Rozenberg G (eds) Lectures on Petri nets II: applications. Advances in Petri nets, vol 1492. Springer, Berlin, pp 1–84
Best E, Devillers R, Koutny M (2001) A consistent model for nets and process algebras. In: Bergstra JA, Ponse A (eds) The handbook on process algebras. North–Holland, Amsterdam, pp 873–944, Chapter 14
Best E, Devillers R, Koutny M (2001) Petri net algebra. EATCS. Springer, Berlin
Best E, Devilllers R, Hall J (1992) The box calculus: a new causal algebra with multi-label communication. In: Rozenberg G (ed) Advances in Petri nets. LNCS, vol 609. Springer, Berlin, pp 21–69
Best E, Koutny M (1995) A refined view of the box algebra. In: De Michelis G, Diaz M (eds) Application and theory of Petri nets 1995, 16th international conference, Turin, Italy. LNCS, vol 935. Springer, Berlin, pp 1–20
Bravetti M, Bernardo M (2000) Compositional asymmetric cooperations for process algebras with probabilities, priorities, and Time. In: Proc of 1st workshop on model for time-critical systems, MTCS 2000. ENTCS, vol 39, issue 3
Hermanns H, Herzog U, Katoen JP (2002) Process algebra for performance evaluation. Theor Comput Sci 274(1–2):43–78
Hermanns H, Rettelbach M (1994) Syntax, semantics, equivalences and axioms for MTIPP. In: Herzog U, Rettelbach M (Eds.) Proc of the 2nd workshop on process algebra and performance modelling, Regensberg/Erlangen, pp 71–88
Hillston J (1994) The nature of the synchronization. In: Herzog U, Rettelbach M (eds), Proc of the second international workshop on process algebra and performance modelling, PAPM 1994, Erlagen, pp 51–70
Hillston J (1996) A compositional approach to performance modelling. Cambridge University Press, Cambridge
Kemeny JG, Snell JL (1960) Finite Markov chains. Van Nostrand, Princeton
Koutny M (2000) A compositional model of time Petri nets. In: Nielsen M, Simpson D (eds) Application and theory of Petri nets 2000, 21st international conference, ICATPN 2000, Aarhus, Denmark, LNCS, vol 1825. Springer, Berlin, pp 303–322
Koutny M, Esparza J, Best E (1994) Operational semantics for the Petri box calculus. In: Jonsson B, Parrow (eds) International conference on concurrency theory, CONCUR’94. LNCS, vol 836. Springer, Berlin, pp 210–255
Larsen K, Skou A (1991) Bisimulation through probabilistic testing. Inf Comput 94(1):1–28
Macià H (2003) sPBC: una extensión Markoviana del Petri box calculus. PhD thesis, Departamento de Informática, Universidad de Castilla-La Mancha (in Spanish)
Macià H, Valero V, Cazorla D, Cuartero F (2004) Introducing the iteration in sPBC. In: de Frutos D, Núñez M (eds) Formal techniques for networked and distributed systems. FORTE 2004, 24th IFIP WG 6.1 international conference, Madrid, Spain. LNCS, vol 3235. Springer, Berlin, pp 292–309
Macià H, Valero V, Cuartero F, Pelayo FL (2003) A new proposal for the synchronization in sPBC. In: Proc of the 3rd international conference on application of concurrent to system design, ACSD 2003, Guimaraes, Portugal. IEEE Computer Society Press, Los Alamitos, pp 216–225
Macià H, Valero V, de Frutos D (2001) sPBC: A Markovian extension of finite Petri box calculus. In: Proc of the 9th IEEE int workshop on Petri nets and performance models, PNPM 2001, Aachen, Germany. IEEE Computer Society, Los Alamitos, pp 207–216
Marroquín O, de Frutos D (2001) Extending the Petri box calculus with time. In: Colom JM, Koutny M (eds) Application and theory of Petri nets 22nd International Conference, ICATPN 2001, Newcastle upon Tyne, UK. LNCS, vol 2075. Springer, Berlin, pp 195–207
Milner R (1989) Communication and concurrency. Prentice Hall International, Englewood
Ribaudo M (1995) Stochastic Petri net semantics for stochastic process algebra. In: Proc of the 6th int workshop on Petri nets and performance models (PNPM’95), Durham. IEEE Computer Society, Englewood, pp 148–157
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Macià, H., Valero, V., Cuartero, F. et al. A congruence relation for sPBC. Form Methods Syst Des 32, 85–128 (2008). https://doi.org/10.1007/s10703-007-0045-2
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10703-007-0045-2