Probabilistic Chemical Abstract Machine and the Expressiveness of Linda Languages

The Chemical Abstract Machine of Berry and Boudol provides a commonly accepted, uniform framework for describing the operational semantics of various process calculi and languages, such as for example CCS, the pi-calculus and coordination languages like Linda. In its original form the CHAM is purely non-deterministic and thus only describes what reactions are `possible' but not how long it will take (in the average) before a certain reaction takes place or its probability. Such quantitative information is however often vital for ``real world'' applications such as systems biology or performance analysis. We propose a probabilistic version of the CHAM. We then define a linear operator semantics for the probabilistic CHAM which exploits a tensor product representation for distributions over possible solutions. Based on this we propose a novel approach towards comparing the expressive power of different calculi via their encoding in the probabilistic CHAM. We illustrate our approach by comparing the expressiveness of various Linda Languages