MobilityReadingGroup

Towards a Categorical Representation of Reversible Event Structures

Eva GRAVERSEN, Iain PHILLIPS, Nobuko YOSHIDA

We study categories for reversible computing, focussing on reversible forms of event structures. Event structures are a well-established model of true concurrency. There exist a number of forms of event structures, including prime event structures, asymmetric event structures, and general event structures. More recently, reversible forms of these types of event structures have been defined. We formulate corresponding categories and functors between them. We show that products and coproducts exist in many cases. In most work on reversible computing, including reversible process calculi, a cause-respecting condition is posited, meaning that the cause of an event may not be reversed before the event itself. Since reversible event structures are not assumed to be cause-respecting in general, we also define cause-respecting subcategories of these event structures. Our longer-term aim is to formulate event structure semantics for reversible process calculi.

@inproceedings{GPY2017,
  author = {Eva Graversen and Iain Phillips and Nobuko Yoshida},
  title = {{Towards a Categorical Representation of Reversible Event Structures}},
  booktitle = {10th International Workshop on Programming Language Approaches to Concurrency- and Communication-cEntric Software},
  series = {EPTCS},
  volume = {246},
  pages = {49--60},
  publisher = {Open Publishing Association},
  year = 2017
}

@inproceedings{GPY2017,
  author = {Eva Graversen and Iain Phillips and Nobuko Yoshida},
  title = {{Towards a Categorical Representation of Reversible Event Structures}},
  booktitle = {10th International Workshop on Programming Language Approaches to Concurrency- and Communication-cEntric Software},
  series = {EPTCS},
  volume = {246},
  pages = {49--60},
  publisher = {Open Publishing Association},
  doi = "10.4204/EPTCS.246.9",
  year = 2017
}