In reversible computations one is interested in the development of mechanisms allowing to undo the effects of executed actions. The past research has been concerned mainly with reversing single actions. In this paper, we consider the problem of reversing the effect of the execution of groups of actions (steps). Using Petri nets as a system model, we introduce concepts related to this new scenario, generalising notions used in the single action case. We then present properties arising when reverse actions are allowed in place/transition nets (pt-nets). We obtain both positive and negative results, showing that allowing steps makes reversibility more problematic than in the interleaving/sequential case. In particular, we demonstrate that there is a crucial difference between reversing steps which are sets and those which are true multisets. Moreover, in contrast to sequential semantics, splitting reverses does not lead to a general method for reversing bounded pt-nets. We then show that a suitable solution can be obtained by combining split reverses with weighted read arcs.
翻译:在可逆的计算中,人们感兴趣的是开发能够消除已执行行动效果的机制。过去的研究主要涉及扭转单个行动。在本文件中,我们考虑了扭转执行一组行动(步骤)影响的问题。使用Petri 网作为系统模型,我们引入了与这一新设想有关的概念,概括了在单一行动情况下使用的概念。然后我们提出了允许采取反向行动/过渡网(顶网)时产生的属性。我们获得了正和负结果,表明允许步骤使反向比中间/顺序案例更成问题。特别是,我们表明,在反向步骤(设置)和真正多套之间存在着关键差异。此外,与顺序定律相反,分裂反向并不导致反向受约束的pt-net(顶网)的一般方法。我们然后表明,通过将分裂反向与加权读弧,可以找到合适的解决办法。