MobilityReadingGroup

Characteristic Bisimulation for Higher-Order Session Processes

Dimitrios KOUZAPAS, Jorge A.PÉREZ, Nobuko YOSHIDA

Characterising contextual equivalence is a long-standing issue for higher-order (process) languages. In the setting of a higher-order π-calculus with sessions, we develop characteristic bisimilarity, a typed bisimilarity which fully characterises contextual equivalence. To our knowledge, ours is the first characterisation of its kind. Using simple values inhabiting (session) types, our approach distinguishes from untyped methods for characterising contextual equivalence in higherorder processes: we show that observing as inputs only a precise finite set of higher-order values suffices to reason about higher-order session processes. We demonstrate how characteristic bisimilarity can be used to justify optimisations in session protocols with mobile code communication.

@article{KPY2017,
  author = {Dimitrios Kouzapas and Jorge A. Pérez and Nobuko Yoshida},
  title = {{Characteristic Bisimulation for Higher-Order Session Processes}},
  journal = {Acta Inf.},
  volume = {54},
  issue = {3},
  pages = {271--341},
  publisher = {Springer},
  year = 2017
}

@article{KPY2017,
  author = {Dimitrios Kouzapas and Jorge A. Pérez and Nobuko Yoshida},
  title = {{Characteristic Bisimulation for Higher-Order Session Processes}},
  journal = {Acta Informatica},
  volume = {54},
  issue = {3},
  pages = {271--341},
  publisher = {Springer},
  doi = "10.1007/s00236-016-0289-7",
  year = 2017
}