Enumeration of reversible functions and its application to circuit complexity

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 pres- ence of negation and permutation and at most in a quadratic number of gates in presence of linear and affine transformations.


Published in:
Proceedings of the 8th Conference on Reversible Computation (RC)
Presented at:
8th Conference on Reversible Computation (RC), Bologna, Italy, July 7-8, 2016
Year:
2016
Publisher:
Cham, Springer
ISBN:
978-3-319-40578-0
978-3-319-40577-3
Keywords:
Laboratories:




 Record created 2016-06-21, last modified 2018-05-09

n/a:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)