Abstract
Name passing calculi are nowadays an established field on its own. Besides their practical relevance, they offered an intriguing challenge, since the standard operational, denotational and logical methods often proved inadequate to reason about these formalisms. A domain which has been successfully employed for languages with asymmetric communication, like the π-calculus, are presheaf categories based on (injective) relabelings, such as \({Set}^\mathbb{I}\). Calculi with symmetric binding, in the spirit of the fusion calculus, give rise to new research problems. In this work we examine the calculus of explicit fusions, and propose to model its syntax and semantics using the presheaf category \({Set}^\mathbb{E}\), where \(\mathbb{E}\) is the category of equivalence relations and equivalence preserving morphisms.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bonchi, F., König, B., Montanari, U.: Saturated semantics for reactive systems. In: Proc. of LICS, pp. 69–80. IEEE, Los Alamitos (2006)
Bonchi, F., Montanari, U.: Coalgebraic models for reactive systems. In: Kok, J.N., Koronacki, J., Lopez de Mantaras, R., Matwin, S., Mladenič, D., Skowron, A. (eds.) ECML 2007. LNCS (LNAI), vol. 4701, pp. 364–380. Springer, Heidelberg (2007)
Bonchi, F., Montanari, U.: Symbolic semantics revisited. In: Amadio, R. (ed.) FOSSACS 2008. LNCS, vol. 4962, pp. 395–412. Springer, Heidelberg (2008)
Boreale, M., Buscemi, M.G., Montanari, U.: D-fusion: A distinctive fusion calculus. In: Chin, W.-N. (ed.) APLAS 2004. LNCS, vol. 3302, pp. 296–310. Springer, Heidelberg (2004)
Boreale, M., Sangiorgi, D.: Some congruence properties for pi-calculus bisimilarities. Theoret. Comput. Sci. 198(1-2), 159–176 (1998)
Buscemi, M.G., Montanari, U.: A first order coalgebraic model of pi-calculus early observational equivalence. In: Brim, L., Jančar, P., Křetínský, M., Kucera, A. (eds.) CONCUR 2002. LNCS, vol. 2421, pp. 449–465. Springer, Heidelberg (2002)
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)
Buscemi, M.G., Montanari, U.: A compositional coalgebraic model of fusion calculus. J. Log. Algebr. Program. 72(1), 78–97 (2007)
Ciancia, V., Montanari, U.: A name abstraction functor for named sets. In: Proc. of CMCS. Elect. Notes in Th. Comput. Sci (to appear, 2008)
Ferrari, G.L., Montanari, U., Pistore, M.: Minimizing transition systems for name passing calculi: A co-algebraic formulation. In: Nielsen, M., Engberg, U. (eds.) FOSSACS 2002. LNCS, vol. 2303, pp. 129–158. Springer, Heidelberg (2002)
Ferrari, G.L., Montanari, U., Tuosto, E.: Coalgebraic minimization of HD-automata for the pi-calculus using polymorphic types. Theoret. Comput. Sci. 331(2-3), 325–365 (2005)
Ferrari, G.L., Montanari, U., Tuosto, E., Victor, B., Yemane, K.: Modelling fusion calculus using HD-automata. In: Fiadeiro, J.L., Harman, N.A., Roggenbach, M., Rutten, J. (eds.) CALCO 2005. LNCS, vol. 3629, pp. 142–156. Springer, Heidelberg (2005)
Fiore, M.P., Moggi, E., Sangiorgi, D.: A fully abstract model for the π-calculus. Inf. Comput. 179(1), 76–117 (2002)
Fiore, M.P., Plotkin, G.D., Turi, D.: Abstract syntax and variable binding. In: Proc. of LICS, pp. 193–202 (1999)
Fiore, M.P., Turi, D.: Semantics of name and value passing. In: Proc. of LICS, pp. 93–104. IEEE, Los Alamitos (2001)
Gabbay, M., Pitts, A.M.: A new approach to abstract syntax with variable binding. Formal Asp. Comput. 13(3-5), 341–363 (2002)
Gadducci, F., Miculan, M., Montanari, U.: About permutation algebras (pre)sheaves and named sets. Higher-Order and Symbolic Computation 19(2-3), 283–304 (2006)
Gadducci, F., Montanari, U.: Graph processes with fusions: Concurrency by colimits, again. In: Kreowski, H.-J., Montanari, U., Orejas, F., Rozenberg, G., Taentzer, G. (eds.) Formal Methods in Software and Systems Modeling. LNCS, vol. 3393, pp. 84–100. Springer, Heidelberg (2005)
Ghani, N., Yemane, K., Victor, B.: Relationally staged computations in calculi of mobile processes. In: The Programming Language Ada. LNCS, vol. 106, pp. 105–120. Springer, Heidelberg (1981)
Giarratana, V., Gimona, F., Montanari, U.: Observability concepts in abstract data type specifications. In: Mazurkiewicz, A. (ed.) MFCS 1976. LNCS, vol. 45, pp. 576–587. Springer, Heidelberg (1976)
Hofmann, M.: Semantical analysis of higher-order abstract syntax. In: Proc. of LICS, pp. 204–213. IEEE, Los Alamitos (1999)
Lanese, I., Montanari, U.: Mapping fusion and synchronized hyperedge replacement into logic programming. Theory Pract. Log. Program. 7(1-2), 123–151 (2007)
Leifer, J.J., Milner, R.: Deriving bisimulation congruences for reactive systems. In: Palamidessi, C. (ed.) CONCUR 2000. LNCS, vol. 1877, pp. 243–258. Springer, Heidelberg (2000)
Miculan, M., Yemane, K.: A unifying model of variables and names. In: Sassone, V. (ed.) FOSSACS 2005. LNCS, vol. 3441, pp. 170–186. Springer, Heidelberg (2005)
Milner, R.: Communication and Concurrency. Prentice-Hall, Englewood Cliffs (1989)
Milner, R., Parrow, J., Walker, D.: A calculus of mobile processes, I and II. Inform. and Comput. 100(1), 1–40 (1992)
Montanari, U., Pistore, M.: An introduction to history dependent automata. In: Proc. of HOOTS. Elect. Notes in Th. Comput. Sci, vol. 10, pp. 170–188 (1997)
Montanari, U., Pistore, M.: Structured coalgebras and minimal HD-automata for the pi-calculus. Theoret. Comput. Sci. 340(3), 539–576 (2005)
Montanari, U., Sassone, V.: Dynamic congruence vs. progressing bisimulation for CCS. Fundamenta Informaticae 16(1), 171–199 (1992)
Parrow, J., Victor, B.: The fusion calculus: Expressiveness and symmetry in mobile processes. In: Proc. of LICS, pp. 176–185. IEEE, Los Alamitos (1998)
Pistore, M.: History Dependent Automata. PhD thesis, Università di Pisa, Dipartimento di Informatica, Available at University of Pisa as PhD. Thesis TD-5/99 (1999)
Plotkin, G.: A structural approach to operational semantics. Technical Report DAIMI FN-19, Aarhus University, Computer Science Department (1981)
Rutten, J.J.M.M.: Universal coalgebra: a theory of systems. Theoret. Comput. Sci. 249(1), 3–80 (2000)
Sangiorgi, D.: A theory of bisimulation for the π-calculus. Acta Inform. 33(1), 69–97 (1996)
Scott, D., Strachey, C.: Toward a mathematical semantics for computer languages. In: Programming Research Group Technical Monograph, Oxford University, Computing Laboratory, vol. PRG-6 (1971)
Stark, I.: A fully abstract domain model for the π-calculus. In: Proc. of LICS, pp. 36–42. IEEE, Los Alamitos (1996)
Turi, D., Plotkin, G.D.: Towards a mathematical operational semantics. In: Proc. of LICS, pp. 280–291. IEEE, Los Alamitos (1997)
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 chapter
Cite this chapter
Bonchi, F., Buscemi, M.G., Ciancia, V., Gadducci, F. (2008). A Category of Explicit Fusions. In: Degano, P., De Nicola, R., Meseguer, J. (eds) Concurrency, Graphs and Models. Lecture Notes in Computer Science, vol 5065. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-68679-8_34
Download citation
DOI: https://doi.org/10.1007/978-3-540-68679-8_34
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-68676-7
Online ISBN: 978-3-540-68679-8
eBook Packages: Computer ScienceComputer Science (R0)