### Young subgroups for reversible computers

(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:
http://hdl.handle.net/1854/LU-676373

- author
- Alexis De Vos UGent and Yvan Van Rentergem
- organization
- year
- 2008
- 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.