Geodesic
On the equality problem of finitely generated classes of exponentially-polynomial functions
Diskretnaya Matematika, Tome 34 (2022) no. 1, pp. 64-75.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DM_2022_34_1_a4,
     author = {S. S. Marchenkov},
     title = {On the equality problem of finitely generated classes of exponentially-polynomial functions},
     journal = {Diskretnaya Matematika},
     pages = {64--75},
     publisher = {mathdoc},
     volume = {34},
     number = {1},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2022_34_1_a4/}
}
TY  - JOUR
AU  - S. S. Marchenkov
TI  - On the equality problem of finitely generated classes of exponentially-polynomial functions
JO  - Diskretnaya Matematika
PY  - 2022
SP  - 64
EP  - 75
VL  - 34
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2022_34_1_a4/
LA  - ru
ID  - DM_2022_34_1_a4
ER  - 
%0 Journal Article
%A S. S. Marchenkov
%T On the equality problem of finitely generated classes of exponentially-polynomial functions
%J Diskretnaya Matematika
%D 2022
%P 64-75
%V 34
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2022_34_1_a4/
%G ru
%F DM_2022_34_1_a4
S. S. Marchenkov. On the equality problem of finitely generated classes of exponentially-polynomial functions. Diskretnaya Matematika, Tome 34 (2022) no. 1, pp. 64-75. http://geodesic.mathdoc.fr/item/DM_2022_34_1_a4/

[1] Darsaliya V. Sh., “Usloviya polnoty dlya polinomov s naturalnymi, tselymi i ratsionalnymi koeffitsientami”, Fundam. i prikl. matem., 2:2 (1996), 365—374 | MR | Zbl

[2] Mamontov A. I., Meshchaninov D. G., “The completeness problem in the function algebra of linear integer-coefficient polynomials”, Discrete Math. Appl., 20:5-6 (2010), 621–641 | DOI | MR | Zbl

[3] Mamontov A. I., Meshchaninov D. G., “The algorithm for completeness recognizing in function algebra $L(\mathbb Z)$”, Discrete Math. Appl., 24:1 (2014), 21–28 | DOI | MR | MR | Zbl

[4] Marchenkov S. S., Funktsionalnye sistemy s operatsiei superpozitsii, Fizmatlit, M., 2004, 104 pp. | MR

[5] Marchenkov S. S., Predstavlenie funktsii superpozitsiyami, KomKniga, M., 2010, 192 pp.

[6] Marchenkov S. S., Izbrannye glavy diskretnoi matematiki, MAKS Press, M., 2016, 133 pp.

[7] Marchenkov S. S., “Completeness criterion in class of exponential-polynomial functions”, Moscow Univ. Comput. Math. and Cybern., 44:2 (2020), 87–94 | DOI | MR | Zbl

[8] Yablonskii S. V., “Funktsionalnye postroeniya v $k$-znachnoi logike”, Sbornik statei po matematicheskoi logike i ee prilozheniyam k nekotorym voprosam kibernetiki, Tr. MIAN SSSR, 51, Izd-vo AN SSSR, M., 1958, 5–142

[9] Rosenberg I. G., “Über die funktionale Vollständigkeit in den mehrwertigen Logiken”, Rozpravy Československé Akad. Věd Řada Mat. Přírod. Věd, 80 (1970), 3–93 | MR