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 functionreversible circuit complexity

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) General theory for finite permutation groups (20B05) 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

• 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?)
• 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
• Invertible Boolean Functions
• On The Number of Symmetry Types of Boolean Functions of n Variables
• On the Classification of Boolean Functions by the General Linear and Affine Groups
• 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)

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

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)