Wyniki wyszukiwania - BazTech

1

Investigating Reversibility of Steps in Petri Nets

de Frutos Escrig David, Koutny Maciej, Mikulski Łukasz

Fundamenta Informaticae

|

2021

|

Vol. 183, nr 1-2

67--96

EN

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.

2

Reversing Transitions in Bounded Petri Nets

Barylska K., Erofeev E., Koutny M., Mikulski Ł., Piątkowski M.

Fundamenta Informaticae

|

2018

|

Vol. 157, nr 4

341--357

EN

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.

3

A Review on Performances of Reversible Ripple-Carry Adders

Burignat S., De Vos A.

International Journal of Electronics and Telecommunications

|

2012

|

Vol. 58, No. 3

205-212

EN

Quantum computing and circuits are of growing interest and so is reversible logic as it plays an important role in the synthesis of quantum circuits. Moreover, reversible logic provides an alternative to classical computing machines, that may overcome many of the power dissipation problems in the near future. Some ripple-carry adders based on a do-spy-undo structure have been designed and tested reversibly. This paper presents a brief overview of the performances obtained with such chips processed in standard 0.35 um CMOS technology and used in true reversible calculation (computations are performed forwards and backwards such that addition and subtraction are made reversibly with the same chip). Adiabatic signals used are known to allow the signal energy stored on the various capacitances of the circuit to be redistributed rather than being dissipated as heat while allowing to avoid calculation errors introduced by the use of conventional rectangular pulses. Through the example of both simulations and experimental results, this paper aims at providing a base of knowledge and knowhow in physical implementation of reversible circuits.

4

On the circuit depth of structurally Reversible Cellular Automata

Kari J.

Fundamenta Informaticae

|

1999

|

Vol. 38, Nr 1,2

93-107

EN

We study the family of structurally reversible cellular automata that use the (generalized) Margolus neighborhoods. We show that every reversible cellular automaton (RCA) can be embedded into the standard two layer Margolus neighborhood defined by two overlapping square partitions of the cellular space and two one-to-one local rules. The embedding allows step-by-step simulations. Then we investigate how many layers of one-to-one local rules are required in exact representations of RCA. We show how in the d-dimensional cellular space any consecutive d+2 layers can be combined into d+1 layers. This proves that no more than d+1 layers are necessary. We demonstrate that in the two-dimensional case d=2 the number d+1 is optimal by providing an example of an RCA with three layers of local rules that cannot be expressed in two layers.