Advanced search

Using group theory in reversible computing

Author
Organization
Abstract
The (2(w))! reversible transformations on w wires, i.e. reversible logic circuits with w inputs and w outputs, together with the action of cascading, form a group, isomorphic to the symmetric group Sew. Therefore, we investigate the group S. as well as one of its subgroups isomorphic to S-n/2 x S-n/2. We then consider the left cosets, the right cosets, and the double cosets generated by the subgroup. Each element of a coset can function as the representative of the coset. Different choices of the coset space and different choices of the coset representatives lead to four different syntheses for implementing an arbitrary reversible logic operation into hardware. Comparison leads to a best choice: a single coset space, with representatives that are generalized TOFFOLI and FREDKIN gates.

Citation

Please use this url to cite or link to this publication:

Chicago
Van Rentergem, Yvan, Alexis De Vos, and Koen De Keyser. 2006. “Using Group Theory in Reversible Computing.” In IEEE Congress on Evolutionary Computation, 2382–2389. New York, NY, USA: IEEE.
APA
Van Rentergem, Yvan, De Vos, A., & De Keyser, K. (2006). Using group theory in reversible computing. IEEE Congress on Evolutionary Computation (pp. 2382–2389). Presented at the IEEE Congress on Evolutionary Computation (CEC 2006), New York, NY, USA: IEEE.
Vancouver
1.
Van Rentergem Y, De Vos A, De Keyser K. Using group theory in reversible computing. IEEE Congress on Evolutionary Computation. New York, NY, USA: IEEE; 2006. p. 2382–9.
MLA
Van Rentergem, Yvan, Alexis De Vos, and Koen De Keyser. “Using Group Theory in Reversible Computing.” IEEE Congress on Evolutionary Computation. New York, NY, USA: IEEE, 2006. 2382–2389. Print.
@inproceedings{411721,
  abstract     = {The (2(w))! reversible transformations on w wires, i.e. reversible logic circuits with w inputs and w outputs, together with the action of cascading, form a group, isomorphic to the symmetric group Sew. Therefore, we investigate the group S. as well as one of its subgroups isomorphic to S-n/2 x S-n/2. We then consider the left cosets, the right cosets, and the double cosets generated by the subgroup. Each element of a coset can function as the representative of the coset. Different choices of the coset space and different choices of the coset representatives lead to four different syntheses for implementing an arbitrary reversible logic operation into hardware. Comparison leads to a best choice: a single coset space, with representatives that are generalized TOFFOLI and FREDKIN gates.},
  author       = {Van Rentergem, Yvan and De Vos, Alexis and De Keyser, Koen},
  booktitle    = {IEEE Congress on Evolutionary Computation},
  isbn         = {9780780394872},
  language     = {eng},
  location     = {Vancouver, BC, Canada},
  pages        = {2382--2389},
  publisher    = {IEEE},
  title        = {Using group theory in reversible computing},
  url          = {http://dx.doi.org/10.1109/CEC.2006.1688605},
  year         = {2006},
}

Altmetric
View in Altmetric
Web of Science
Times cited: