Abstract
In this paper, the concept of complete finite prefixes for process algebra expressions is extended to stochastic models. Events are supposed to happen after a delay that is determined by random variables assigned to the preceding conditions. Max-plus algebra expressions are shown to provide an elegant notation for stochastic prefixes not containing any decisions. Furthermore, they allow for the computation of performance measures. The derivation of the so called k-th occurrence times is shown in detail.
This is a preview of subscription content, log in via an institution to check access.
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
F. Baccelli, A. Jean-Marie, and Zhen Liu. A survey on solution methods for task graph models. In N. Gotz, U. Herzog, and M. Rettelbach, editors, Proc. of the QMIPS-Workshop on Formalism, Principles and State-of-the-art. Arbeitsberichte des IMMD 26(14). Universität Erlangen, 1993.
F. L. Baccelli, G. Cohen, G. J. Olsder, and J.-P. Quadrat. Synchronization and Linearity. An Algebra for Discrete Event Systems. John Wiley & Sons, 1992.
E. Brinksma, J.-P. Katoen, R. Langerak, and D. Latella. A stochastic causality-based process algebra. The Computer Journal, 38(7):552–565, 1995.
L. Cloth. Complete finite prefix for stochastic process algebra. Master’s thesis, RWTH Aachen, Department of Computer Science, 2000. available at ftp://ftp-lvs.informatik.rwth-aachen.de/pub/da/2000/cloth.ps.gz.
J. Esparza, S. Romer, and W. Vogler. An improvement of McMillan’s unfolding algorithm. In T. Margaria and B. Steffen, editors, Proc. of TACAS’96, LNCS 1055, pages 87–106. Springer, 1996.
P. Glynn. A GSMP formalism for discrete event simulation. Proc. of the IEEE, 77(1):14–23, 1989.
J.-P. Katoen. Quantitative and Qualitative Extensions of Event Structures. PhD thesis, Universiteit Twente, 1996.
J.-P. Katoen, E. Brinksma, D. Latella, and R. Langerak. Stochastic simulation of event structures. In M. Ribaudo, editor, Proc. of PAPM 1996, pages 21–40. C.L.U.T. Press, 1996.
R. Langerak and H. Brinksma. A complete finite prefix for process algebra. In CAV’99, LNCS 1663, pages 184–195. Springer, 1999.
K. L. McMillan. Symbolic Model Checking, chapter 9: A Partial Order Approach, pages 153–167. Kluwer, 1993.
V. Mertsiotakis and M. Silva. A throughput approximation algorithm for decision free processes. In M. Ribaudo, editor, Proc. of PAPM 1996, pages 161–178. C.L.U.T. Press, 1996.
G. Olsder, J. Resing, R. de Vries, M. Keane, and G. Hooghiemstra. Discrete event systems with stochastic processing times. IEEE Transactions on Automatic Control, 35(3):299–302, 1990.
T. C. Ruys, R. Langerak, J.-P. Katoen, D. Latella, and M. Massink. First passage time analysis of stochastic process algebra using partial orders. In T. Margaria and W. Yi, editors, Proc. of TACAS 2001, LNCS 2031, pages 220–235. Springer, 2001.
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
Cloth, L., Bohnenkamp, H., Haverkort, B. (2001). Using Max-Plus Algebra for the Evaluation of Stochastic Process Algebra Prefixes. In: de Alfaro, L., Gilmore, S. (eds) Process Algebra and Probabilistic Methods. Performance Modelling and Verification. PAPM-PROBMIV 2001. Lecture Notes in Computer Science, vol 2165. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44804-7_10
Download citation
DOI: https://doi.org/10.1007/3-540-44804-7_10
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42556-4
Online ISBN: 978-3-540-44804-4
eBook Packages: Springer Book Archive