Graph Transformation Meets Reversible Circuits: Model Transformation and Optimization

Reversible circuits provide the subject of a new promising direction of circuit design. Reversible circuits are cascades of reversible gates specifying bijective functions on Boolean vectors. As one encounters quite a variety of reversible gates in the literature, there are many classes of reversible circuits. Two main problems are considered: (1) How can circuits of one class be transformed into the ones of another class? (2) How can circuits within one class be optimized with respect to certain measures? While reversible circuits are studied on the functional level and on the level of propositional calculus, there is also a visual representation used frequently for illustrative purposes in an informal way. In this paper, the visual description of reversible circuits is formalized by means of graph transformation. In particular, it is shown that the problems of model transformation and optimization can be investigated within the graph-transformational framework. This continues the authors’ earlier work on the generation, evaluation and synthesis of reversible circuits as graphs.