|
Problemy Peredachi Informatsii, 2009, Volume 45, Issue 3, Pages 56–72
(Mi ppi1989)
|
|
|
|
Automata Theory
The smallest known length of an ordered system of generators of a symmetric group
S. A. Kalinchuka, Yu. L. Sagalovichb a NetCracker, Moscow
b A. A. Kharkevich Institute for Information Transmission Problems, Russian Academy of Sciences
Abstract:
We consider a recursive algorithm for constructing an ordered system of generators of a symmetric group of degree $n$. We show that the number of transpositions that form this system is $O(n\log_2^2n)$. This is only by a factor of $\log_2n$ greater in order than the lower bound on the number of transpositions in such a system.
Received: 16.12.2008 Revised: 22.06.2009
Citation:
S. A. Kalinchuk, Yu. L. Sagalovich, “The smallest known length of an ordered system of generators of a symmetric group”, Probl. Peredachi Inf., 45:3 (2009), 56–72; Problems Inform. Transmission, 45:3 (2009), 242–257
Linking options:
https://www.mathnet.ru/eng/ppi1989 https://www.mathnet.ru/eng/ppi/v45/i3/p56
|
Statistics & downloads: |
Abstract page: | 274 | Full-text PDF : | 84 | References: | 45 | First page: | 2 |
|