Using \(\pi\)DDs in the design of reversible circuits. (English) Zbl 1451.68107

Glück, Robert (ed.) et al., Reversible computation. 4th international workshop, RC 2012, Copenhagen, Denmark, July 2–3, 2012. Revised papers. Berlin: Springer. Lect. Notes Comput. Sci. 7581, 197-203 (2013).
Summary: With \(\pi\)DDs a data structure has recently been introduced that offers a compact representation for sets of permutations. Since reversible functions constitute permutations on the input assignments, they can naturally be expressed using this data structure. However, its potential has not been exploited so far. In this work-in-progress report, we present and discuss possible applications of \(\pi\)DDs within the design of reversible circuits including techniques for synthesis, debugging, and an efficient determination of the number of minimal circuits. We observed that \(\pi\)DDs inhibit the same space complexities as truth tables and, hence, do not superior existing design methods in many cases. However, they are advantageous when dealing with several functions or gates at once.
For the entire collection see [Zbl 1322.68013].


68Q06 Networks and circuits as models of computation; circuit complexity
68P05 Data structures
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)


Full Text: DOI


This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.