Session Type Isomorphisms

Mariangiola Dezani-Ciancaglini
(Universita' di Torino)
Luca Padovani
(Universita' di Torino)
Jovanka Pantovic
(Univerzitet u Novom Sadu)

There has been a considerable amount of work on retrieving functions in function libraries using their type as search key. The availability of rich component specifications, in the form of behavioral types, enables similar queries where one can search a component library using the behavioral type of a component as the search key. Just like for function libraries, however, component libraries will contain components whose type differs from the searched one in the order of messages or in the position of the branching points. Thus, it makes sense to also look for those components whose type is different from, but isomorphic to, the searched one.

In this article we give semantic and axiomatic characterizations of isomorphic session types. The theory of session type isomorphisms turns out to be subtle. In part this is due to the fact that it relies on a non-standard notion of equivalence between processes. In addition, we do not know whether the axiomatization is complete. It is known that the isomorphisms for arrow, product and sum types are not finitely axiomatisable, but it is not clear yet whether this negative results holds also for the family of types we consider in this work.

In Alastair F. Donaldson and Vasco T. Vasconcelos: Proceedings 7th Workshop on Programming Language Approaches to Concurrency and Communication-cEntric Software (PLACES 2014), Grenoble, France, 12 April 2014, Electronic Proceedings in Theoretical Computer Science 155, pp. 61–71.
Published: 12th June 2014.

ArXived at: http://dx.doi.org/10.4204/EPTCS.155.9 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org