• Previous Article
    A note on the order bound on the minimum distance of AG codes and acute semigroups
  • AMC Home
  • This Issue
  • Next Article
    On an improved correlation analysis of stream ciphers using multi-output Boolean functions and the related generalized notion of nonlinearity
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]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

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

Zhenyu Zhang, Lijia Ge, Fanxin Zeng, Guixin Xuan. Zero correlation zone sequence set with inter-group orthogonal and inter-subgroup complementary properties. Advances in Mathematics of Communications, 2015, 9 (1) : 9-21. doi: 10.3934/amc.2015.9.9

[17]

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

[18]

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

[19]

Joel Hass, Michael Hutchings and Roger Schlafly. The double bubble conjecture. Electronic Research Announcements, 1995, 1: 98-102.

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

2017 Impact Factor: 0.564

Metrics

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

Other articles
by authors

[Back to Top]