Reversibility and asymmetric conflict in event structures

•We introduce reversible forms of event structures.•To control how events are reversed, we use asymmetric conflict on events.•We use mixed forward and reverse transition steps, and limits of non-monotone sequences.•Among other results, we show when reachable configurations which are finite are reachable finitely.•We discuss reversing in causal order as well as forms of non-causal reversing.

Reversible computation has attracted increasing interest in recent years, with applications in hardware, software and biochemistry. We introduce reversible forms of prime event structures and asymmetric event structures. In order to control the manner in which events are reversed, we use asymmetric conflict on events. We prove a number of results about reachable configurations; for instance, we show under what conditions reachable configurations which are finite are reachable by purely finite means. We discuss, with examples, reversing in causal order, where an event is only reversed once all events it caused have been reversed, as well as forms of non-causal reversing.