\`x^2+y_1+z_12^34\`
Advanced Search
Advanced Search
Advanced Search
This issue Previous Article Next Article
Article Contents
Article Contents
2008, Volume 2, Issue 2: 183-200. Doi: 10.3934/amc.2008.2.183
This issue Previous Article A note on the order bound on the minimum distance of AG codes and acute semigroups Next Article On an improved correlation analysis of stream ciphers using multi-output Boolean functions and the related generalized notion of nonlinearity

Young subgroups for reversible computers

  • 1.

    Imec v.z.w. and Vakgroep elektronika en informatiesystemen, Universiteit Gent, Sint Pietersnieuwstraat 41, B - 9000 Gent

  • 2.

    Vakgroep elektronika en informatiesystemen, Universiteit Gent, Sint Pietersnieuwstraat 41, B - 9000 Gent

Received:  November 2007
Revised:  February 2008
Published:  May 2008
Abstract Related Papers Cited by
    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_q^p$. This leads to synthesis methods for arbitrary reversible logic circuits of logic width $w$. These circuits form a group isomorphic to $S$2w. 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.
    Mathematics Subject Classification: 05A05, 20B35, 68Q10, 94C10.

    Citation:
    shu

    \begin{equation} \\ \end{equation}
    • Related Papers
  • Cited by
  • Access History
  • 加载中
PDF
XML
Export Citation
SHARE
Email to a Friend

Article Metrics

HTML views() PDF downloads(329) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return
    Site map Copyright © 2023 American Institute of Mathematical Sciences