RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2008 Volume 20, Issue 4, Pages 61–78 (Mi dm1026)

This article is cited in 4 papers

Finite generability of some groups of recursive permutations

S. A. Volkov


Abstract: Let a class $\mathcal Q$ of functions of natural argument be closed with respect to a superposition and contain the identity function. The set of permutations $f$ such that $f,f^{-1}\in\mathcal Q$ forms a group (with respect to the operation of composition) which we denote by $Gr(\mathcal Q)$. We prove the finite generability of $Gr(\mathcal Q)$ for a large family of classes $\mathcal Q$ satisfying some conditions. As an example, we consider the class $\mathrm{FP}$ of functions which are computable in polynomial time by a Turing machine. The obtained result is generalised to the classes $\mathscr E^n$ of the Grzegorczyk system, $n\ge2$.
It is proved that for the considered classes $\mathcal Q$ the minimum number of permutations generating the group $Gr(\mathcal Q)$ is equal to two. More exactly, there exist two permutations of the given group such that any permutation of this group can be obtained by compositions of these permutations.

UDC: 519.7

Received: 22.06.2007

DOI: 10.4213/dm1026


 English version:
Discrete Mathematics and Applications, 2008, 18:6, 607–624

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025