Affiliations: [a] Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Toruń, Chopina 12/18, Poland. kamila.barylska@mat.umk.pl | [b] Parallel Systems, Department of Computing Science, Carl von Ossietzky Universität, D-26111 Oldenburg, Germany. evgeny.erofeev@informatik.uni-oldenburg.de | [c] School of Computing Science, Newcastle University, Newcastle upon Tyne, NE1 7RU, United Kingdom. maciej.koutny@newcastle.ac.uk | [d] Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Toruń, Chopina 12/18, Poland. lukasz.mikulski@mat.umk.pl | [e] Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Toruń, Chopina 12/18, Poland. marcin.piatkowski@mat.umk.pl
Note: [*] Partially supported by the Polish grant No.2013/09/D/ST6/03928
Note: [†] Partially supported by DFG (German Research Foundation) through grant Be 1267/14-1 (Design and Analysis Methods for Real-Time Systems) and Graduiertenkolleg GRK-1765 (System Correctness under Adverse Conditions). Address for correspondence: Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, ul. Chopina 12/18, 87-100 Toruń, Poland
Abstract: Reversible computation deals with mechanisms for undoing the effects of actions executed by a dynamic system. This paper is concerned with reversibility in the context of Petri nets which are a general formal model of concurrent systems. A key construction we investigate amounts to adding ‘reverse’ versions of selected net transitions. Such a static modification can severely impact on the behaviour of the system, e.g., the problem of establishing whether the modified net has the same states as the original one is undecidable. We therefore concentrate on nets with finite state spaces and show, in particular, that every transition in such nets can be reversed using a suitable set of new transitions.
Keywords: Petri net, reversibility, reversible computation
