zbMATH — the first resource for mathematics

Interactive Markov chains. (English) Zbl 0937.60065
Arbeitsberichte des Instituts für Mathematische Maschinen und Datenverarbeitung (Informatik), Universität Erlangen-Nürnberg. 32, 7. Erlangen-Nürnberg: Universität Erlangen-Nürnberg, x, 252 p. (1999).
Summary: Markov chains are widely used as stochastic models to study and estimate performance characteristics of various nature. In this dissertation we address the issue of compositional specification and analysis of continuous time Markov chains. Based on principles known from process algebra, we develop an algebra of Interactive Markov Chains (IMC) arising as an orthogonal extension of both Markov chains and process algebra. In this algebra the interrelation of delays and actions is governed by the notion of maximal progress: Internal actions are executed without letting time pass, while external actions are potentially delayed. The claim that IMC are more than ‘yet another’ formalism to describe Markov chains is justified by a number of distinguishing results of both theoretical and practical nature. Among others, we develop an algebraic theory of IMC, devise algorithms to mechanise compositional aggregations of IMC, and successfully apply compositional aggregation to analyse state spaces of several millions of states, resulting from a study of an ordinary telephony system.

60J27 Continuous-time Markov processes on discrete state spaces