Abstract
The concurrent constraint pi-calculus (cc-pi-calculus) has been introduced as a model for concluding Service Level Agreements. The cc-pi calculus combines the synchronous communication paradigm of process calculi with the constraint handling mechanism of concurrent constraint programming. While in the original presentation of the calculus a reduction semantics has been proposed, in this work we investigate the abstract semantics of cc-pi processes. First, we define a labelled transition system of the calculus and a notion of open bisimilarity à la pi-calculus that is proved to be a congruence. Next, we give a symbolic characterisation of bisimulation and we prove that the two semantics coincide. Essentially, two processes are open bisimilar if they have the same stores of constraints - this can be statically checked - and if their moves can be mutually simulated. A key idea of the symbolic transition system is to have ‘contextual’ labels, i.e. labels specifying that a process can evolve only in presence of certain constraints. Finally, we show that the polyadic Explicit Fusions calculus introduced by Gardner and Wischik can be translated into monadic cc-pi and that such a transition preserves open bisimilarity. The mapping exploits fusions and tuple unifications as constraints.
Research supported by the EU IST-FP6 16004 Integrated Project Sensoria.
Chapter PDF
Similar content being viewed by others
Keywords
- Service Level Agreement
- Label Transition System
- Process Calculus
- Reduction Semantic
- Structural Congruence
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
Abadi, M., Fournet, C.: Mobile values, new names, and secure communication. In: POPL 2001: Proceedings of the 28th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 104–115. ACM Press, New York (2001)
Bistarelli, S., Gadducci, F.: Enhancing constraints manipulation in semiring-based formalisms. In: ECAI, pp. 63–67. IOS Press, Amsterdam (2006)
Bistarelli, S., Montanari, U., Rossi, F.: Semiring-based constraint satisfaction and optimization. Journal of the ACM 44(2), 201–236 (1997)
Boreale, M., De Nicola, R.: A symbolic semantics for the pi-calculus. Inf. Comput. 126(1), 34–52 (1996)
Buscemi, M.G., Montanari, U.: Cc-pi: A constraint-based language for specifying service level agreements. In: De Nicola, R. (ed.) ESOP 2007. LNCS, vol. 4421, pp. 18–32. Springer, Heidelberg (2007)
Diaz, J.F., Rueda, C., Valencia, F.: A calculus for concurrent processes with constraints. CLEI Electronic Journal 1(2) (1998)
Gilbert, D., Palamidessi, C.: Concurrent Constraint Programming with Process Mobility. In: Palamidessi, C., Moniz Pereira, L., Lloyd, J.W., Dahl, V., Furbach, U., Kerber, M., Lau, K.-K., Sagiv, Y., Stuckey, P.J. (eds.) CL 2000. LNCS (LNAI), vol. 1861, pp. 463–477. Springer, Heidelberg (2000)
Hennessy, M., Lin, H.: Symbolic bisimulations. Theor. Comp. Sci. 138, 353–389 (1995)
Milner, R., Parrow, J., Walker, J.: A calculus of mobile processes, I and II. Inform. and Comput., 100(1), 1–40,41–77 (1992)
Palamidessi, C., Valencia, F.: A Temporal Concurrent Constraint Programming Calculus. In: Walsh, T. (ed.) CP 2001. LNCS, vol. 2239, pp. 302–316. Springer, Heidelberg (2001)
Rudeanu, S., Vaida, D.: Semirings in operations research and computer science. Fundam. Inf. 61(1), 61–85 (2004)
Sangiorgi, D.: A theory of bisimulation for the π-calculus. Acta Inform. 33, 69–97 (1996)
Saraswat, V.: Concurrent Constraint Programming. PhD thesis, Carnegie Mellon University (1993)
Saraswat, V., Rinard, M.: Concurrent constraint programming. In: Proc. POPL 1990. ACM Press (1990)
Wischik, L., Gardner, P.: Strong Bisimulation for the Explicit Fusion Calculus. In: Walukiewicz, I. (ed.) FOSSACS 2004. LNCS, vol. 2987, pp. 484–498. Springer, Heidelberg (2004)
Wischik, L., Gardner, P.: Explicit fusions. Theoret. Comput. Sci. 340(3), 606–630 (2005)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Buscemi, M.G., Montanari, U. (2008). Open Bisimulation for the Concurrent Constraint Pi-Calculus. In: Drossopoulou, S. (eds) Programming Languages and Systems. ESOP 2008. Lecture Notes in Computer Science, vol 4960. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78739-6_20
Download citation
DOI: https://doi.org/10.1007/978-3-540-78739-6_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-78738-9
Online ISBN: 978-3-540-78739-6
eBook Packages: Computer ScienceComputer Science (R0)