Core higher-order session processes: tractable equivalences and relative expressiveness
File(s)DTR15-1.pdf (490.27 KB)
Published version
OA Location
Author(s)
Kouzapas, D
Pérez, JA
Yoshida, N
Type
Report
Abstract
This work proposes tractable bisimulations for the higher-order -
calculus with session primitives (HO ) and o ers a complete study of the expressivity
of its most significant subcalculi. First we develop three typed bisimulations,
which are shown to coincide with contextual equivalence. These characterisations
demonstrate that observing as inputs only a specific finite set of
higher-order values (which inhabit session types) su ces to reason about HO
processes. Next, we identify HO, a minimal, second-order subcalculus of HO
in which higher-order applications/abstractions, name-passing, and recursion are
absent. We show that HO can encode HO extended with higher-order applications
and abstractions and that a first-order session -calculus can encode HO .
Both encodings are fully abstract. We also prove that the session -calculus with
passing of shared names cannot be encoded into HO without shared names. We
show that HO , HO, and are equally expressive; the expressivity of HO enables
e ective reasoning about typed equivalences for higher-order processes.
calculus with session primitives (HO ) and o ers a complete study of the expressivity
of its most significant subcalculi. First we develop three typed bisimulations,
which are shown to coincide with contextual equivalence. These characterisations
demonstrate that observing as inputs only a specific finite set of
higher-order values (which inhabit session types) su ces to reason about HO
processes. Next, we identify HO, a minimal, second-order subcalculus of HO
in which higher-order applications/abstractions, name-passing, and recursion are
absent. We show that HO can encode HO extended with higher-order applications
and abstractions and that a first-order session -calculus can encode HO .
Both encodings are fully abstract. We also prove that the session -calculus with
passing of shared names cannot be encoded into HO without shared names. We
show that HO , HO, and are equally expressive; the expressivity of HO enables
e ective reasoning about typed equivalences for higher-order processes.
Date Issued
2015-01-01
Citation
Logic in Computer Science, Departmental Technical Report: 15/1, 2015, pp.1-90
Publisher
Department of Computing, Imperial College London
Start Page
1
End Page
90
Journal / Book Title
Logic in Computer Science
Departmental Technical Report: 15/1
Copyright Statement
© 2015 The Author(s). This report is available open access under a CC-BY-NC-ND (https://creativecommons.org/licenses/by-nc-nd/4.0/)
Sponsor
Engineering & Physical Science Research Council (EPSRC)
Engineering & Physical Science Research Council (E
Engineering & Physical Science Research Council (E
Engineering and Physical Sciences Research Council
Grant Number
EP/K011715/1
ERI 025567 (EP/K034413/1)
PO 20131167
EP/L00058X/1, PO 20131167
Publication Status
Published
Article Number
15/1