American Institute of Mathematical Sciences

Advanced
  • Previous Article
    On an improved correlation analysis of stream ciphers using multi-output Boolean functions and the related generalized notion of nonlinearity
  • AMC Home
  • This Issue
  • Next Article
    A note on the order bound on the minimum distance of AG codes and acute semigroups
May  2008, 2(2): 183-200. doi: 10.3934/amc.2008.2.183

Young subgroups for reversible computers

Alexis De Vos 1, and  Yvan Van Rentergem 2,

1. 

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

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

Received  November 2007 Revised  February 2008 Published  April 2008

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.
Keywords: Reversible computing, Young subgroup, double coset enumeration..
Mathematics Subject Classification: 05A05, 20B35, 68Q10, 94C1.
Citation: Alexis De Vos, Yvan Van Rentergem. Young subgroups for reversible computers. Advances in Mathematics of Communications, 2008, 2 (2) : 183-200. doi: 10.3934/amc.2008.2.183
[1]

Jinsong Xu. Reversible hidden data access algorithm in cloud computing environment. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1219-1232. doi: 10.3934/dcdss.2019084
[2]

Yves Guivarc'h. On the spectrum of a large subgroup of a semisimple group. Journal of Modern Dynamics, 2008, 2 (1) : 15-42. doi: 10.3934/jmd.2008.2.15
[3]

Stefano Luzzatto, Marks Ruziboev. Young towers for product systems. Discrete & Continuous Dynamical Systems, 2016, 36 (3) : 1465-1491. doi: 10.3934/dcds.2016.36.1465
[4]

Daniel T. Wise. Nonpositive immersions, sectional curvature, and subgroup properties. Electronic Research Announcements, 2003, 9: 1-9.

[5]

Marco Castrillón López, Pedro Luis García Pérez. The problem of Lagrange on principal bundles under a subgroup of symmetries. Journal of Geometric Mechanics, 2019, 11 (4) : 539-552. doi: 10.3934/jgm.2019026
[6]

Sheena D. Branton. Sub-actions for young towers. Discrete & Continuous Dynamical Systems, 2008, 22 (3) : 541-556. doi: 10.3934/dcds.2008.22.541
[7]

Konstantinos Drakakis, Francesco Iorio, Scott Rickard, John Walsh. Results of the enumeration of Costas arrays of order 29. Advances in Mathematics of Communications, 2011, 5 (3) : 547-553. doi: 10.3934/amc.2011.5.547
[8]

Konstantinos Drakakis, Francesco Iorio, Scott Rickard. The enumeration of Costas arrays of order 28 and its consequences. Advances in Mathematics of Communications, 2011, 5 (1) : 69-86. doi: 10.3934/amc.2011.5.69
[9]

Johan Chrisnata, Han Mao Kiah, Sankeerth Rao Karingula, Alexander Vardy, Eitan Yaakobi Yao, Hanwen Yao. On the number of distinct k-decks: Enumeration and bounds. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021032
[10]

Masahiro Yamaguchi, Yasuhiro Takeuchi, Wanbiao Ma. Population dynamics of sea bass and young sea bass. Discrete & Continuous Dynamical Systems - B, 2004, 4 (3) : 833-840. doi: 10.3934/dcdsb.2004.4.833
[11]

Steffen Arnrich. Modelling phase transitions via Young measures. Discrete & Continuous Dynamical Systems - S, 2012, 5 (1) : 29-48. doi: 10.3934/dcdss.2012.5.29
[12]

G. Dal Maso, Antonio DeSimone, M. G. Mora, M. Morini. Time-dependent systems of generalized Young measures. Networks & Heterogeneous Media, 2007, 2 (1) : 1-36. doi: 10.3934/nhm.2007.2.1
[13]

Joscha Diehl, Jianfeng Zhang. Backward stochastic differential equations with Young drift. Probability, Uncertainty and Quantitative Risk, 2017, 2 (0) : 5-. doi: 10.1186/s41546-017-0016-5
[14]

Hideyuki Suzuki, Shunji Ito, Kazuyuki Aihara. Double rotations. Discrete & Continuous Dynamical Systems, 2005, 13 (2) : 515-532. doi: 10.3934/dcds.2005.13.515
[15]

Paul H. Rabinowitz. On a class of reversible elliptic systems. Networks & Heterogeneous Media, 2012, 7 (4) : 927-939. doi: 10.3934/nhm.2012.7.927
[16]

Katherine Morrison. An enumeration of the equivalence classes of self-dual matrix codes. Advances in Mathematics of Communications, 2015, 9 (4) : 415-436. doi: 10.3934/amc.2015.9.415
[17]

James C. Robinson. Computing inertial manifolds. Discrete & Continuous Dynamical Systems, 2002, 8 (4) : 815-833. doi: 10.3934/dcds.2002.8.815
[18]

Claudio A. Buzzi, Jeroen S.W. Lamb. Reversible Hamiltonian Liapunov center theorem. Discrete & Continuous Dynamical Systems - B, 2005, 5 (1) : 51-66. doi: 10.3934/dcdsb.2005.5.51
[19]

Antonio Pumariño, Claudia Valls. On the double pendulum: An example of double resonant situations. Discrete & Continuous Dynamical Systems, 2004, 11 (2&3) : 413-448. doi: 10.3934/dcds.2004.11.413
[20]

Seok-Jin Kang and Jae-Hoon Kwon. Quantum affine algebras, combinatorics of Young walls, and global bases. Electronic Research Announcements, 2002, 8: 35-46.

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (261)
  • HTML views (0)
  • Cited by (21)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy