|
On the equality problem of finitely generated classes of exponentially-polynomial functions
S. S. Marchenkov Lomonosov Moscow State University
Abstract:
We consider the class $\mathrm{EP}_{\mathbb N}$ of exponentially-polynomial functions which can be obtained by arbitrary superpositions of the constants 0, 1 and arithmetic operations of addition, multiplication, and powering. For this class, we solve the algorithmic equality problem of two functions that assume a finite number of values. Next, this class is restricted to the class $\mathrm{PEP}_{\mathbb N}$, in which the function $x^y$ is replaced by a sequence of functions $\{p_i^x\}$, where $p_0, p_1,\ldots$ are all prime numbers. For the class $\mathrm{PEP}_{\mathbb N}$, the problem of membership of a function to a finitely generated class is effectively reduced to the equality problem of two functions. In turn, the last problem is effectively solved for the set of all one-place $\mathrm{PEP}_{\mathbb N}$-functions.
Keywords:
exponentially-polynomial functions, equality problem.
Received: 15.04.2021
Citation:
S. S. Marchenkov, “On the equality problem of finitely generated classes of exponentially-polynomial functions”, Diskr. Mat., 34:1 (2022), 64–75; Discrete Math. Appl., 33:3 (2023), 167–175
Linking options:
https://www.mathnet.ru/eng/dm1666https://doi.org/10.4213/dm1666 https://www.mathnet.ru/eng/dm/v34/i1/p64
|
Statistics & downloads: |
Abstract page: | 225 | Full-text PDF : | 48 | References: | 52 | First page: | 6 |
|