Ghent University Academic Bibliography

Advanced

Young subgroups for reversible computers

Alexis De Vos UGent and Yvan Van Rentergem (2008) ADVANCES IN MATHEMATICS OF COMMUNICATIONS. 2(2). p.183-200
abstract
We consider the symmetric group S-n in the special case where n is composite: n = pq (both p and q being integer). Applying Birkhoff's theorem, we prove that an arbitrary element of S-pq can be decomposed into a product of three permutations, the first and the third being elements of the Young subgroup S-p(q), whereas the second one is an element of the dual Young subgroup S-p(q). This leads to synthesis methods for arbitrary reversible logic circuits of logic width w. These circuits form a group isomorphic to S(2)w. A particularly efficient synthesis is found by choosing p = 2 and thus q = 2(w-1). The approach illustrates a direct link between combinatorics, group theory, and reversible computing.
Please use this url to cite or link to this publication:
author
organization
year
type
journalArticle (original)
publication status
published
subject
keyword
Young subgroup, reversible computing, double coset enumeration
journal title
ADVANCES IN MATHEMATICS OF COMMUNICATIONS
Adv. Math. Commun.
volume
2
issue
2
pages
183 - 200
publisher
American Institute of Mathematical Sciences
place of publication
Springfield, MO, USA
Web of Science type
Article
Web of Science id
000256120100006
JCR category
MATHEMATICS, APPLIED
JCR impact factor
0.97 (2008)
JCR rank
59/175 (2008)
JCR quartile
2 (2008)
ISSN
1930-5346
language
English
UGent publication?
yes
classification
A1
id
676373
handle
http://hdl.handle.net/1854/LU-676373
date created
2009-06-03 14:34:23
date last changed
2009-07-01 09:06:24
@article{676373,
  abstract     = {We consider the symmetric group S-n in the special case where n is composite: n = pq (both p and q being integer). Applying Birkhoff's theorem, we prove that an arbitrary element of S-pq can be decomposed into a product of three permutations, the first and the third being elements of the Young subgroup S-p(q), whereas the second one is an element of the dual Young subgroup S-p(q). This leads to synthesis methods for arbitrary reversible logic circuits of logic width w. These circuits form a group isomorphic to S(2)w. A particularly efficient synthesis is found by choosing p = 2 and thus q = 2(w-1). The approach illustrates a direct link between combinatorics, group theory, and reversible computing.},
  author       = {De Vos, Alexis and Van Rentergem, Yvan},
  issn         = {1930-5346},
  journal      = {ADVANCES IN MATHEMATICS OF COMMUNICATIONS},
  keyword      = {Young subgroup,reversible computing,double coset enumeration},
  language     = {eng},
  number       = {2},
  pages        = {183--200},
  publisher    = {American Institute of Mathematical Sciences},
  title        = {Young subgroups for reversible computers},
  volume       = {2},
  year         = {2008},
}

Chicago
De Vos, Alexis, and Yvan Van Rentergem. 2008. “Young Subgroups for Reversible Computers.” Advances in Mathematics of Communications 2 (2): 183–200.
APA
De Vos, Alexis, & Van Rentergem, Y. (2008). Young subgroups for reversible computers. ADVANCES IN MATHEMATICS OF COMMUNICATIONS, 2(2), 183–200.
Vancouver
1.
De Vos A, Van Rentergem Y. Young subgroups for reversible computers. ADVANCES IN MATHEMATICS OF COMMUNICATIONS. Springfield, MO, USA: American Institute of Mathematical Sciences; 2008;2(2):183–200.
MLA
De Vos, Alexis, and Yvan Van Rentergem. “Young Subgroups for Reversible Computers.” ADVANCES IN MATHEMATICS OF COMMUNICATIONS 2.2 (2008): 183–200. Print.