• 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

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.
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 - A, 2016, 36 (3) : 1465-1491. doi: 10.3934/dcds.2016.36.1465

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[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]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

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

[19]

Santiago Cañez. Double groupoids and the symplectic category. Journal of Geometric Mechanics, 2018, 10 (2) : 217-250. doi: 10.3934/jgm.2018009

[20]

Michael Hutchings, Frank Morgan, Manuel Ritore and Antonio Ros. Proof of the double bubble conjecture. Electronic Research Announcements, 2000, 6: 45-49.

2018 Impact Factor: 0.879

Metrics

  • PDF downloads (23)
  • HTML views (0)
  • Cited by (11)

Other articles
by authors

[Back to Top]