Finite Bases with Respect to the Superposition in Classes of Elementary Recursive Functions, dissertation

This is a thesis that was defended in 2009 at Lomonosov Moscow State University. In Chapter 1:

It is proved that that the class of lower (Skolem) elementary functions is the set of all polynomial-bounded functions that can be obtained by a composition of $x + 1$ , $x y$ , $\max (x - y, 0)$ , $x \land y$ , $⌊ x / y ⌋$ , and one exponential function ( $2^{x}$ or $x^{y}$ ) using formulas that have no more than 2 floors with respect to an exponent (for example, $(x + y)^{x y + z} + 1$ has 2 floors, $2^{2^{x}}$ has 3 floors). Here $x \land y$ is a bitwise AND of $x$ and $y$ .
It is proved that ${x+y,\ \max(x-y,0),\ x\wedge y,\ \lfloor x/y \rfloor,
2^{\lfloor \log_2 x \rfloor^2}} $a n d$ {x+y,\ \max(x-y,0),\ x\wedge y,
\lfloor x/y \rfloor,\ x^{\lfloor \log_2 y \rfloor}}$ are composition bases in the functional version of the uniform ${T C}^{0}$ (also known as $F O M$ ).
The hierarchy of classes exhausting the class of elementary functions is described in terms of compositions with restrictions on a number of floors in a formula. The results of Chapter 1 are published in:

Volkov S.A. An exponential expansion of the Skolem-elementary functions, and bounded superpositions of simple arithmetic functions (in Russian), Mathematical Problems of Cybernetics, Moscow, Fizmatlit, 2007, vol. 16, pp. 163-190
doi:10.1134/S1064562407040217 In Chapter 2 a simple composition basis in the class $E^{2}$ of Grzegorczyk hierarchy is described. This result is published in DOI: 10.1515/156939206779238436 In Chapter 3 it is proved that the group of permutations $G r (Q) = {f : f, f^{- 1} \in Q}$ is generated by two permutations for many classes $Q$ . For example, this is proved for $Q = F P$ , where $F P$ is the class of all polynomial-time computable functions (of the length of input). The results of chapter 3 are published in DOI: 10.1515/DMA.2008.046

This is a thesis that was defended in 2009 at Lomonosov Moscow State University. In Chapter 1:

It is proved that that the class of lower (Skolem) elementary functions is the set of all polynomial-bounded functions that can be obtained by a composition of $x + 1$ , $x y$ , $\max (x - y, 0)$ , $x \land y$ , $⌊ x / y ⌋$ , and one exponential function ( $2^{x}$ or $x^{y}$ ) using formulas that have no more than 2 floors with respect to an exponent (for example, $(x + y)^{x y + z} + 1$ has 2 floors, $2^{2^{x}}$ has 3 floors). Here $x \land y$ is a bitwise AND of $x$ and $y$ .
It is proved that ${x+y,\ \max(x-y,0),\ x\wedge y,\ \lfloor x/y \rfloor,
2^{\lfloor \log_2 x \rfloor^2}} $a n d$ {x+y,\ \max(x-y,0),\ x\wedge y,
\lfloor x/y \rfloor,\ x^{\lfloor \log_2 y \rfloor}}$ are composition bases in the functional version of the uniform ${T C}^{0}$ (also known as $F O M$ ).
The hierarchy of classes exhausting the class of elementary functions is described in terms of compositions with restrictions on a number of floors in a formula. The results of Chapter 1 are published in:

Volkov S.A. An exponential expansion of the Skolem-elementary functions, and bounded superpositions of simple arithmetic functions (in Russian), Mathematical Problems of Cybernetics, Moscow, Fizmatlit, 2007, vol. 16, pp. 163-190
doi:10.1134/S1064562407040217 In Chapter 2 a simple composition basis in the class $E^{2}$ of Grzegorczyk hierarchy is described. This result is published in DOI: 10.1515/156939206779238436 In Chapter 3 it is proved that the group of permutations $G r (Q) = {f : f, f^{- 1} \in Q}$ is generated by two permutations for many classes $Q$ . For example, this is proved for $Q = F P$ , where $F P$ is the class of all polynomial-time computable functions (of the length of input). The results of chapter 3 are published in DOI: 10.1515/DMA.2008.046

文献摘要