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 structure have been defined. We formulate corresponding categories and functors between them. We show that products and coproducts exist in many cases.

We define stable reversible general event structures and stable configuration systems, and we obtain an isomorphism between the subcategory of the former in normal form and the finitely enabled subcategory of the latter.

In most work on reversible computing, including reversible process calculi, a causality 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 causal in general, we also define causal subcategories of these event structures.

@article{GPY2019,
  author = {Eva Graversen and Iain Phillips and Nobuko Yoshida},
  title = {{Towards a Categorical Representation of Reversible Event Structures}},
  journal = {JLAMP},
  volume = {104},
  pages = {16--59},
  publisher = {Elsevier},
  year = 2019
}

@article{GPY2019,
  author = {Eva Graversen and Iain Phillips and Nobuko Yoshida},
  title = {{Towards a Categorical Representation of Reversible Event Structures}},
  journal = {Journal of Logical and Algebraic Methods in Programming},
  volume = {104},
  pages = {16--59},
  publisher = {Elsevier},
  doi = "10.1016/j.jlamp.2019.01.001",
  year = 2019
}