Towards a categorical representation of reversible event structures
File(s)1704.03099.pdf (173.28 KB)
Published version
Author(s)
Graversen, E
Phillips, ICC
Yoshida, N
Type
Conference Paper
Abstract
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 co-
products 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 re-
versed 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.
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 co-
products 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 re-
versed 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.
Date Issued
2017-04-08
Date Acceptance
2017-03-08
Citation
Electronic Proceedings in Theoretical Computer Science, EPTCS, 2017, 246, pp.49-60
ISSN
2075-2180
Publisher
Open Publishing Association
Start Page
49
End Page
60
Journal / Book Title
Electronic Proceedings in Theoretical Computer Science, EPTCS
Volume
246
Copyright Statement
© 2017 E. Graversen, I. Phillips, & N. Yoshida
This work is licensed under the
Creative Commons Attribution License.
This work is licensed under the
Creative Commons Attribution License.
Sponsor
Engineering & Physical Science Research Council (E
Engineering & Physical Science Research Council (E
Engineering & Physical Science Research Council (EPSRC)
Commission of the European Communities
Engineering & Physical Science Research Council (EPSRC)
Engineering & Physical Science Research Council (E
Grant Number
ERI 025567 (EP/K034413/1)
PO 1553380
EP/K011715/1
612985
EP/N027833/1
72043/2
Source
10th International Workshop on Programming Language Approaches to Concurrency- and Communication-cEntric Software (PLACES 2017)
Subjects
cs.LO
Publication Status
Published
Start Date
2017-04-29
Coverage Spatial
Uppsala, Sweden