On the Relative Expressiveness of Higher-Order Session Processes
File(s)paper.pdf (242.37 KB)
Accepted version
Author(s)
Kouzapas, D
Perez, J
Yoshida, N
Type
Conference Paper
Abstract
By integrating constructs from the λλ-calculus and the ππ-calculus, in higher-order process calculi exchanged values may contain processes. This paper studies the relative expressiveness of HOπHOπ, the higher-order ππ-calculus in which communications are governed by session types. Our main discovery is that HOHO, a subcalculus of HOπHOπ which lacks name-passing and recursion, can serve as a new core calculus for session-typed higher-order concurrency. By exploring a new bisimulation for HOHO, we show that HOHO can encode HOπHOπ fully abstractly (up to typed contextual equivalence) more precisely and efficiently than the first-order session ππ-calculus (ππ). Overall, under session types, HOπHOπ, HOHO, and ππ are equally expressive; however, HOπHOπ and HOHO are more tightly related than HOπHOπ and ππ.
Date Issued
2016-03-22
Date Acceptance
2015-12-18
Citation
Lecture Notes in Computer Science, 2016, 9632, pp.446-475
ISSN
0302-9743
Publisher
Springer
Start Page
446
End Page
475
Journal / Book Title
Lecture Notes in Computer Science
Volume
9632
Copyright Statement
The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-662-49498-1_18
Sponsor
Engineering & Physical Science Research Council (E
Engineering & Physical Science Research Council (E
Engineering & Physical Science Research Council (EPSRC)
Commission of the European Communities
Grant Number
ERI 025567 (EP/K034413/1)
PO 1553380
EP/K011715/1
612985
Source
ESOP 2016
Subjects
Artificial Intelligence & Image Processing
08 Information And Computing Sciences
Publication Status
Published
Start Date
2016-04-02
Finish Date
2016-04-08
Coverage Spatial
Eindhoven, The Netherlands