Abstract
The Chemical Abstract Machine (CHAM) 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 π 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.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Banâtre, J.P., Le Métayer, D.: The gamma model and its discipline of programming. Science of Computer Programming 15, 55–77 (1990)
Banâtre, J.P., Fradet, P., Le Métayer, D.: Gamma and the chemical reaction model: Fifteen years after. In: Calude, C.S., Pun, G., Rozenberg, G., Salomaa, A. (eds.) Multiset Processing. LNCS, vol. 2235, pp. 17–44. Springer, Heidelberg (2001)
Fradet, P., Le Métayer, D.: Structured gamma. Science of Computer Programming 31, 263–289 (1998)
Le Métayer, D.: Higher-order multiset programming. In: DIMACS workshop on specifications of parallel algorithms. Dimacs series in Discrete Mathematics, vol. 18. American Mathematical Society, Providence (1994)
Andreoli, J.M., Hankin, C., Le Métayer, D.: Coordination Programming. Imperial College Press, London (1996)
Berry, G., Boudol, G.: The chemical abstract machine. Theoretical Computer Science 96, 217–248 (1992)
Jonsson, B., Yi, W., Larsen, K.: 11. In: Probabilistic Extensions of Process Algebras, pp. 685–710. Elsevier Science, Amsterdam (2001); see [16]
De Nicola, R., Ferrari, G., Pugliese, R.: KLAIM: A kernel language for agents interaction and mobility. IEEE Transactions on Software Engineering 24, 315–330 (1998)
Grimmett, G., Stirzaker, D.: Probability and Random Processes, 2nd edn. Clarendon Press, Oxford (1992)
Parzen, E.: Stochastic Processes. In: Classics in Applied Mathematics, 2nd edn. SIAM, Philadelphia (1999)
Ciancarini, P., Jensen, K., Yankelevich, D.: On the operational semantics of a coordination language. In: Ciancarini, P., Nierstrasz, O., Yonezawa, A. (eds.) ECOOP-WS 1994. LNCS, vol. 924. Springer, Heidelberg (1995)
Shapiro, E.: Embeddings among concurrent programming languages. In: Cleaveland, W.R. (ed.) CONCUR 1992. LNCS, vol. 630, pp. 486–503. Springer, Heidelberg (1992)
de Boer, F.S., Palamidessi, C.: Embedding as a tool for language comparison. Information and Computation 108, 128–157 (1994)
Brogi, A., Di Pierro, A., Wiklicky, H.: Linear embedding for a quantitative comparison of language expressiveness. In: QAPL 2001 — ACM Workshop on Quantitative Aspects of Programming Languages. ENTCS, vol. 59(3). Elsevier, Amsterdam (2002)
Palamidessi, C.: Comparing the expressive power of the synchronous and the asynchronous pi-calculus. Mathematical Structures in Computer Science 13, 685–719 (2003)
Bergstra, J., Ponse, A., Smolka, S. (eds.): Handbook of Process Algebra. Elsevier Science, Amsterdam (2001)
Palmer, T.: Banach Algebras and The General Theory of *-Algebras – Volume I: Algebras and Banach Algebras. Encyclopedia of Mathematics and Its Applications, vol. 49. Cambridge University Press, Cambridge (1994)
Kadison, R., Ringrose, J.: Fundamentals of the Theory of Operator Algebras: Volume I — Elementary Theory. In: Graduate Studies in Mathematics, vol. 15, American Mathematical Society, Providence, Rhode Island (1997); Reprint from Academic Press edition (1983)
Fillmore, P.A.: A User’s Guide to Operator Algebras. Ohn Wiley & Sons, Chichester (1996)
Wegge-Olsen, N.: K-Theory and C*-Algebras — A Friendly Approach. Oxford University Press, Oxford (1993)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Di Pierro, A., Hankin, C., Wiklicky, H. (2006). On a Probabilistic Chemical Abstract Machine and the Expressiveness of Linda Languages. In: de Boer, F.S., Bonsangue, M.M., Graf, S., de Roever, WP. (eds) Formal Methods for Components and Objects. FMCO 2005. Lecture Notes in Computer Science, vol 4111. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11804192_18
Download citation
DOI: https://doi.org/10.1007/11804192_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-36749-9
Online ISBN: 978-3-540-36750-5
eBook Packages: Computer ScienceComputer Science (R0)