Enumeration of reversible functions and its application to circuit complexity

DOI10.1007/978-3-319-40578-0_19MaRDI QIDQ3186605zbMATH OpenOpenAlexFDO

Authors Mathias Soeken, Nabila Abdessaied, Giovanni De Micheli

Publication date 10 August 2016

Published in Reversible Computation (Search for Journal in Brave)

Full work available at URL https://infoscience.epfl.ch/record/218884/files/2016_rc_2.pdf

zbMATH Keywords

equivalence classpermutation groupreversible circuit complexityreversible function

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) General theory for finite permutation groups (20B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Switching theory, applications of Boolean algebras to circuits and networks (94C11) Boolean functions (94D10)

Recommendations

• scientific article; zbMATH DE number 2163011
• The classification of reversible bit operations
• Realization and synthesis of reversible functions
• The complexity of the representation of multiple-output Boolean functions
• Computing the number of the equivalence classes for reversible logic functions

Cites work

• A Study of Optimal 4-Bit Reversible Toffoli Circuits and Their Synthesis
• Detection of Total or Partial Symmetry of a Switching Function with the Use of Decomposition Charts
• Equivalence classes of invertible Boolean functions
• scientific article; zbMATH DE number 3138899 (Why is no real title available?)
• scientific article; zbMATH DE number 4068961 (Why is no real title available?)
• scientific article; zbMATH DE number 3692653 (Why is no real title available?)
• Invertible Boolean Functions
• On the Classification of Boolean Functions by the General Linear and Affine Groups
• On The Number of Symmetry Types of Boolean Functions of n Variables
• The Number of Classes of Invertible Boolean Functions
• The Number of Transitivity Sets of Boolean Functions
• White dots do matter: rewriting reversible logic circuits

Cited in

(13)

• A library of reversible circuit transformations (work in progress)
• Computing the number of the equivalence classes for reversible logic functions
• Application of Functional Decomposition in Synthesis of Reversible Circuits
• GENERALIZED COUNTERS AND REVERSAL COMPLEXITY
• An approximate algorithm for computing the complexity of reversible functions in the basis of Toffoli
• The classification of reversible bit operations
• scientific article; zbMATH DE number 2163011 (Why is no real title available?)
• On the number of reversible homogeneous structures
• scientific article; zbMATH DE number 822043 (Why is no real title available?)
• A spectral algorithm for 3-valued function equivalence classification
• scientific article; zbMATH DE number 2209891 (Why is no real title available?)
• An Algorithm for Linear, Affine and Spectral Classification of Boolean Functions
• New Results on Reversible Boolean Functions Having Component Functions with Specified Properties

This page was built for publication: Enumeration of reversible functions and its application to circuit complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3186605)