Advanced Search
Article Contents
Article Contents

Young subgroups for reversible computers

Abstract / Introduction Related Papers Cited by
  • 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.


    \begin{equation} \\ \end{equation}
  • 加载中

Article Metrics

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

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint