Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-26T05:52:14.855Z Has data issue: false hasContentIssue false
  • English
  • Français

Order algebras: a quantitative model of interaction

Published online by Cambridge University Press:  13 February 2017

EMMANUEL BEFFARA
EMMANUEL BEFFARA*
Affiliation:
Institut de Mathématiques de Luminy, Aix Marseille Université, CNRS, Centrale Marseille, I2M, UMR 7373, 13453, Marseille, France Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

A quantitative model of concurrent interaction is introduced. The basic objects are linear combinations of partial order relations, acted upon by a group of permutations that represents potential non-determinism in synchronisation. This algebraic structure is shown to provide faithful interpretations of finitary process algebras, for an extension of the standard notion of testing semantics, leading to a model that is both denotational (in the sense that the internal workings of processes are ignored) and non-interleaving. Constructions on algebras and their subspaces enjoy a good structure that make them (nearly) a model of differential linear logic, showing that the underlying approach to the representation of non-determinism as linear combinations is the same.

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. 1126 - 1168
Copyright
Copyright © Cambridge University Press 2017 

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

Abbes, S. and Benveniste, A. (2006). True-concurrency probabilistic models: Branching cells and distributed probabilities for event structures. Information and Computation, 204 (2) 231–274.Google Scholar
Abramsky, S., Jagadeesan, R. and Malacaria, P. (1994). Full abstraction for PCF. In: International Symposium on Theoretical Aspects of Computer Science (TACS), 1–15.Google Scholar
Akian, M., Gaubert, S. and Guterman, A. (2009). Linear independence over tropical semirings and beyond. In: Litvinov, G.L. and Sergeev, S.N., (eds.), Proceedings of the International Conference on Tropical and Idempotent Mathematics, volume 495 of Contemporary Mathematics, 1–38, AMS.Google Scholar
Baillot, P., Danos, V., Ehrhard, T. and Regnier, L. (1997). Believe it or not, AJM's games model is a model of classical linear logic. In: LICS, 68–75.Google Scholar
Beffara, E. (2008). An algebraic process calculus. In: Proceedings of the Twenty-Third Annual IEEE Symposium on Logic in Computer Science (LICS), 130–141.Google Scholar
Beffara, E. (2009). Quantitative Testing Semantics for Non-Interleaving. Technical Report hal-00397551, Institut de Mathématiques de Luminy. Available at http://hal.archives-ouvertes.fr/hal-00397551/.Google Scholar
Boreale, M. and Gadducci, F. (2003). Denotational testing semantics in coinductive form. In: Rovan, B. and Vojtáš, P. (eds.) Mathematical Foundations of Computer Science 2003, volume 2747 of Lecture Notes in Computer Science, 279–289, Springer.Google Scholar
Boreale, M. and Gadducci, F. (2006). Processes as formal power series: A coinductive approach to denotational semantics. Theoretical Computer Science, 360 440–458.CrossRefGoogle Scholar
Boudol, G. and Castellani, I. (1988). A non-interleaving semantics for CCS based on proved transitions. Fundamenta Informaticae, XI 433–453.Google Scholar
Ciancia, V. and Montanari, U. (2010). Symmetries, local names and dynamic (de)-allocation of names. Information and Computation, 208 (12) 1349–1367.Google Scholar
Crafa, S., Varacca, D. and Yoshida, N. (2007). Compositional event structure semantics for the π-calculus. In: Proceedings of the 18th International Conference on Concurrency Theory (CONCUR), volume 4703 of Lecture Notes in Computer Science, 317–332, Springer.Google Scholar
Darondeau, P. and Degano, P. (1989). Causal trees. In: Ausiello, G., Dezani-Ciancaglini, M., and Della Rocca, S. (eds.) International Conference Automata, Languages and Programming, volume 372 of Lecture Notes in Computer Science, 234–248, Springer.Google Scholar
de Nicola, R. and Hennessy, M. (1984). Testing equivalences for processes. Theoretical Computer Science, 34 83–133.CrossRefGoogle Scholar
Diekert, V. and Rozenberg, G. (1995). The Book of Traces, World Scientific Publishing Co.CrossRefGoogle Scholar
Ehrhard, T. and Laurent, O. (2007). Interpreting a finitary π-calculus in differential interaction nets. In: Caires, L. and Vasconcelos, V.T. (eds.) 18th International Conference on Concurrency Theory (Concur), volume 4703 of LNCS, 333–348, Springer.Google Scholar
Ehrhard, T. and Regnier, L. (2003). The differential λ-calculus. Theoretical Computer Science, 309 (1) 1–41.Google Scholar
Ehrhard, T. and Regnier, L. (2006). Differential interaction nets. Theoretical Computer Science, 364 (2) 166–195.CrossRefGoogle Scholar
Faggian, C. and Piccolo, M. (2009). Partial orders, event structures and linear strategies. In: Typed Lambda Calculi and Applications, volume 5608 of Lecture Notes in Computer Science, 95–111, Springer.Google Scholar
Gabbay, M.J. (2011). Foundations of nominal techniques: logic and semantics of variables in abstract syntax. Bulletin of Symbolic Logic. In press.Google Scholar
Hoare, C.A.R. (1985). Communicating Sequential Processes. Prentice Hall.Google Scholar
Hyland, J.M.E. and Ong, C.-H.L. (2000). On full abstraction for PCF (parts I, II and III). Information and Computation, 163 (2) 285–408.Google Scholar
Lamport, L. (1978). Time, clocks and the ordering of events in a distributed system. Communications of the ACM, 21 (7) 558–565.Google Scholar
Lang, S. (1965). Algebra, Addison-Wesley.Google Scholar
Loday, J.-L. (2008). Generalized bialgebras and triples of operads. Astérisque, 317.Google Scholar
Melliès, P.-A. and Mimram, S. (2008). From asynchronous games to concurrent games. Submitted.Google Scholar
Milner, R. (1989). Communication and concurrency, Prentice Hall.Google Scholar
Milner, R. (1999). Communicating and Mobile Systems: the π-Calculus, Cambridge University Press.Google Scholar
Montanari, U. and Pistore, M. (2005). Structured coalgebras and minimal HD-automata for the π-calculus. Theoretical Computer Science, 340 (3) 539–576.Google Scholar
Olderog, E.-R. and Hoare, C.A.R. (1986). Specification-oriented semantics for communicating processes. Acta Informatica, 23 (1) 9–66.CrossRefGoogle Scholar
Pin, J.-E. (1994). Tropical semirings. In: Gunawardena, J. (ed.) Idempotency (Bristol, 1994), volume 11 of Publications of the Newton Institute, 50–69, Cambridge University Press.Google Scholar
Rutten, J.J.M.M. (1999). Automata, power series, and coinduction: Taking input derivatives seriously. In: Wiedermann, J., van Emde Boas, P., and Nielsen, M. (eds.) Internatioanl Conference on Automata, Languages and Programming (ICALP), volume 1644 of Lecture Notes in Computer Science, 707–707, Springer.Google Scholar
Sangiorgi, D. (1996). π-calculus, internal mobility and agent-passing calculi. Theoretical Computer Science, 167 (2) 235–274.Google Scholar
Staton, S. and Winskel, G. (2010). On the expressivity of symmetry in event structures. In: Proceedings of the 25th Annual IEEE Symposium on Logic in Computer Science, LICS 2010, 392–401, IEEE Computer Society.CrossRefGoogle Scholar
Varacca, D., Völzer, H., and Winskel, G. (2006). Probabilistic event structures and domains. Theoretical Computer Science, 358 (2–3) 173–199.Google Scholar
Winskel, G. (1982). Event structure semantics for CCS and related languages. In: Proceedings of the 9th International Colloquium on Automata, Languages and Programming (ICALP), volume 140 of Lecture Notes in Computer Science, 561–576, Springer.CrossRefGoogle Scholar
Winskel, G. (1987). Event structures. In: Brauer, W. and Reisig, W. and Rozenberg, G. (eds.) Advances in Petri nets: applications and relationships to other models of concurrency, volume 255 of Lecture Notes in Computer Science 325–392, Springer-Verlag, Berlin, Heidelberg.Google Scholar
Winskel, G. (2007). Event structures with symmetry. Electronic Notes in Theoretical Computer Science, 172:611–652. Computation, Meaning, and Logic: Articles dedicated to Gordon Plotkin.Google Scholar