Hostname: page-component-78c5997874-t5tsf Total loading time: 0 Render date: 2024-11-13T09:26:15.416Z Has data issue: false hasContentIssue false
  • English
  • Français

The true concurrency of differential interaction nets

Published online by Cambridge University Press:  21 November 2016

DAMIANO MAZZA
DAMIANO MAZZA*
Affiliation:
CNRS, UMR 7030, Laboratoire d'Informatique de Paris Nord, Université Paris 13, Sorbonne Paris Cité, F-93430 Villetaneuse, France Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We analyse the reduction of differential interaction nets from the point of view of so-called ‘true concurrency,’ that is, employing a non-interleaving model of parallelism. More precisely, we associate with each differential interaction net an event structure describing its reduction. We show how differential interaction nets are only able to generate confusion-free event structures, and we argue that this is a serious limitation in terms of the concurrent behaviours they may express. In fact, confusion is an extremely elementary phenomenon in concurrency (for example, it already appears in CCS with just prefixing and parallel composition) and we show how its presence is preserved by any encoding respecting the degree of distribution and the reduction semantics. We thus infer that no reasonably expressive process calculus may be satisfactorily encoded in differential interaction nets. We conclude with an analysis of one such encoding proposed by Ehrhard and Laurent, and argue that it does not contradict our claims, but rather supports them.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 28 , Special Issue 7: Differential Linear Logic, Nets and Other Quantitative and Parallel Approaches to Proof-Theory , August 2018 , pp. 1097 - 1125
Copyright
Copyright © Cambridge University Press 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Abramsky, S. (1993). Computational interpretations of linear logic. Theoretical Computer Science 111 (1–2) 3–57.Google Scholar
Abramsky, S. (1994). Proofs as processes. Theoretical Computer Science 135 (1) 5–9.Google Scholar
Alexiev, V. (1999). Non-deterministic Interaction Nets. Ph.D. Thesis, University of Alberta.Google Scholar
Baldan, P., Corradini, A., Montanari, U. and Ribeiro, L. (2007). Unfolding semantics of graph transformation. Information Computation 205 (5) 733–782.Google Scholar
Bellin, G. and Scott, P.J. (1994). On the pi-calculus and linear logic. Theoretical Computer Science 135 (1) 11–65.Google Scholar
Boldi, P., Cardone, F. and Sabadini, N. (1993). Concurrent automata, prime event structures and universal domains. In: Droste, M. and Gurevich, Y. (eds.) Semantics of Programming Languages and Model Theory, Algebra, Logic and Applications, vol. 5, Gordon and Breach, 89–108.Google Scholar
Caires, L. and Pfenning, F. (2010). Session types as intuitionistic linear propositions. In: Gastin, P. and Laroussinie, F. (eds.) Proceedings of CONCUR 2010, Lecture Notes in Computer Science, vol. 6269, Springer, 222–236.Google Scholar
Clark, D. and Kennaway, R. (1996). Event structures and non-orthogonal term graph rewriting. Mathematical Structures in Computer Science 6 (6) 545–578.Google Scholar
Crafa, S., Varacca, D. and Yoshida, N. (2012). Event structure semantics of parallel extrusion in the pi-calculus. In: Birkedal, L. (ed.) Proceedings of FoSSaCS 2012, Lecture Notes in Computer Science, vol. 7213, Springer, 225–239.Google Scholar
Dorman, A. (2013). Concurrency in Interaction Nets and Graph Rewriting. Ph.D. Thesis, Università degli Studi Roma Tre / Université Paris Nord-Sorbonne Paris Cité.Google Scholar
Ehrhard, T. (2005). Finiteness spaces. Mathematical Structures in Computer Science 15 (4) 615–646.Google Scholar
Ehrhard, T. and Laurent, O. (2010a). Acyclic solos and differential interaction nets. Logical Methods in Computer Science 6 (3).Google Scholar
Ehrhard, T. and Laurent, O. (2010b). Interpreting a finitary Pi-calculus in differential interaction nets. Information and Computation 208 (6) 606–633.CrossRefGoogle Scholar
Ehrhard, T. and Regnier, L. (2006). Differential interaction nets. Theoretical Computer Science 364 (2) 166–195.Google Scholar
Girard, J.-Y. (1987). Linear logic. Theoretical Computer Science 50 (1) 1–102.Google Scholar
Girard, J.-Y. (1996). Proof-nets: The parallel syntax for proof-theory. In: Ursini and Agliano (eds.), Logic and Algebra. Marcel Dekker, Inc.Google Scholar
Gorla, D. (2010). Towards a unified approach to encodability and separation results for process calculi. Information and Computation 208 (9) 1031–1053.Google Scholar
Honda, K. and Laurent, O. (2010). An exact correspondence between a typed pi-calculus and polarised proof-nets. Theoretical Computer Science 411 (22–24) 2223–2238.Google Scholar
Khasidashvili, Z. and Glauert, J.R.W. (2005). The conflict-free reduction geometry. Theoretical Computer Science 347 (3) 465–497.Google Scholar
Kobayashi, N., Pierce, B.C. and Turner, D.N. (1999). Linearity and the Pi-Calculus. ACM Transactions on Programming Languages and Systems 21 (5) 914–947.Google Scholar
Lafont, Y. (1990). Interaction nets. In: Conference Record of POPL'90, ACM Press, 95–108.Google Scholar
Lafont, Y. (1997). Interaction combinators. Information and Computation 137 (1) 69–101.Google Scholar
Laneve, C., Parrow, J. and Victor, B. (2001). Solo diagrams. In: Kobayashi, N. and Pierce, B.C. (eds.) Proceedings of TACS 2001, Lecture Notes in Computer Science, vol. 2215, Springer, 127–144.Google Scholar
Laneve, C. and Victor, B. (2003). Solos in concert. Mathematical Structures in Computer Science 13 (5) 657–683.Google Scholar
Mazurkiewicz, A.W. (1986). Trace theory. In: Brauer, W., Reisig, W. and Rozenberg, G. (eds.) Advances in Petri Nets, Lecture Notes in Computer Science, vol. 255, Springer, 279–324.Google Scholar
Mazza, D. (2005). Multiport interaction nets and concurrency. In: Abadi, M. and de Alfaro, L. (eds.) In: Proceedings of CONCUR 2005, Lecture Notes in Computer Science, Springer, 21–35.CrossRefGoogle Scholar
Mazza, D. (2006). Interaction nets: Semantics and concurrent extensions. Ph.D. Thesis, Université de la Méditerranée / Università degli Studi Roma Tre.Google Scholar
Melliès, P.-A. (2004). Asynchronous games 2: The true concurrency of innocence. Theoretical Computer Science 358 (2–3) 200–228.CrossRefGoogle Scholar
Mimram, S. (2008). Sémantique des jeux asynchrone et réécriture 2-dimensionelle. Ph.D. Thesis, Université Paris-Diderot (Paris 7).Google Scholar
Nielsen, M., Plotkin, G.D. and Winskel, G. (1981). Petri nets, event structures and domains, part I. Theoretical Computer Science 13 (1) 85–108.Google Scholar
Parrow, J. (2008). Expressiveness of process algebras. Electronic Notes in Theoretical Computer Science 209 173–186.CrossRefGoogle Scholar
Parrow, J. and Sjodin, P. (1992). Multiway synchrinizaton verified with coupled simulation. In: Cleaveland, R. (ed.) Proceedings of CONCUR'92, Lecture Notes in Computer Science (LNCS), vol. 630, Springer, 518–533.CrossRefGoogle Scholar
Parrow, J. and Victor, B. (1998). The fusion calculus: Expressiveness and symmetry in mobile processes. In: Proceedings of LICS, IEEE Computer Society, 176–185.Google Scholar
Rabinovitch, A. and Traktenbrot, B. (1988). Behaviour structures and nets. Fundamenta Informatica 11 (4) 357–404.Google Scholar
Rozenberg, G. and Engelfriet, J. (1996). Elementary net systems. In: Dagstuhl Lectures on Petri Nets, Lecture Notes in Computer Science, vol. 1491, Springer, 12–121.Google Scholar
Stark, E.W. (1989). Concurrent transition systems. Theoretical Computer Science 64 (3) 221–269.Google Scholar
van Glabeek, R.J. and Goltz, U. (1989). Equivalence notions for concurrent systems and refinement of actions. In: Proceedings of MFCS 1989, Lecture Notes in Computer Science (LNCS), vol. 379, Springer-Verlag.Google Scholar
Varacca, D., Völzer, H. and Winskel, G. (2006). Probabilistic event structures and domains. Theoretical Computer Science 358 (2–3) 173–199.CrossRefGoogle Scholar
Winskel, G. (1982). Event structure semantics of CCS and related languages. In: Nielsen, M. and Schmidt, E.M. (eds.), Proceedings of ICALP 1982, Lecture Notes in Computer Science vol. 140, Springer, 561–576.Google Scholar
Winskel, G. and Nielsen, M. (1995). Models for concurrency. In: Handbook of Logic in Computer Science, vol. 4, Oxford University Press.Google Scholar
Wischik, L. and Gardner, P. (2005). Explicit fusions. Theoretical Computer Science 340 (3) 606–630.Google Scholar
Yoshida, N., Berger, M. and Honda, K. (2004). Strong normalisation in the pi-calculus. Information and Computation 191 (2) 145–202.CrossRefGoogle Scholar