Skip to main content Skip to main navigation

Publication

Enumeration of reversible functions and its application to circuit complexity

Mathias Soeken; Nabila Abdessaied; Giovanni De Micheli
In: Mathias Soeken; Nabila Abdessaied; Giovanni De Micheli. Reversible Computation. Pages 125-137, Springer, 2016.

Abstract

We review combinational results to enumerate and classify reversible functions and investigate the application to circuit complexity. In particularly, we consider the effect of negating and permuting input and output variables and the effect of applying linear and affine transformations to inputs and outputs. We apply the results to reversible circuits and prove that minimum circuit realizations of functions in the same equivalence class differ at most in a linear number of gates in presence of negation and permutation and at most in a quadratic number of gates in presence of linear and affine transformations.