Probabilistic rewrite strategies: Applications to ELAN

Abstract. Recently rule based languages focussed on the use of rewrit-ing as a modeling tool which results in making specications executable. To extend the modeling capabilities of rule based languages, we explore the possibility of making the rule applications subject to probabilistic choices. We propose an extension of the ELAN strategy language to deal with randomized systems. We argue through several examples that we propose indeed a natural setting to model systems with randomized choices. This leads us to interesting new problems, and we address the generalization of the usual concepts in abstract reduction systems to randomized systems.