A probabilistic language formalism for stochastic discrete-event systems

The formalism of probabilistic languages has been introduced for modeling t he qualitative behavior of stochastic discrete-event systems. A probabilist ic language is a unit interval-valued map over the set of traces of the sys tem satisfying certain consistency constraints. Regular language operators such as choice, concatenation, and Kleene-closure have been defined in the setting of probabilistic languages to allow modeling of complex systems in terms of simpler ones. The set of probabilistic languages is closed under s uch operators, thus forming an algebra. It also is a complete partial order under a natural ordering in which the operators are continuous. Hence, rec ursive equations can be solved in this algebra. This is alternatively deriv ed by using the contraction mapping theorem on the set of probabilistic lan guages which is shown to be a complete metric space. The notion of regulari ty, i.e., finiteness of automata representation, of probabilistic languages has been defined and it is shown that regularity is preserved under choice , concatenation, and Kleene-closure. We show that this formalism is also us eful in describing system performance measures such as completion time, rel iability, etc., and present properties to aide their computation.