Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2017, 11:4, 545-553
Volume 24, No 4, 2017, P. 60-76
UDC 519.716
S. S. Marchenkov
On the operations of bounded suffix summation and multiplication
Abstract:
The operations of bounded suffix summation and bounded suffix multiplication are introduced. Using these operations, we define the class BSSM of polynomially computable functions. It is proved that the class BSSM contains the class BPC defined by the operation of bounded prefix concatenation and has finite basis under superposition.
Bibliogr. 13.
Keywords: bounded suffix summation, bounded suffix multiplication.
DOI: 10.17377/daio.2017.24.558
Sergey S. Marchenkov 1
1. Lomonosov Moscow State University,
1 Leninskie gory, 119991 Moscow, Russia
e-mail: ssmarchen@yandex.ru
Received 30 November 2016
References
[1] S. A. Volkov, An example of a simple quasi-universal function in the class $\mathscr E^2$ of the Grzegorczyk hierarchy, Diskretn. Mat., 18, No. 4, 31–44, 2006 [Russian]. Translated in Discrete Math. Appl., 16, No. 5, 513–526, 2006.[2] A. I. Maltsev, Iterative algebras and Post manifolds, Algebra Logika, 5, No. 2, 5–24, 1966 [Russian].
[3] A. I. Maltsev, Iterativnye algebry Posta (Iterative Post Algebras), Izd. NGU, Novosibirsk, 1976 [Russian].
[4] S. S. Marchenkov, Elimination of recursion schemas in the Grzegorczyk class $\mathscr E^2$, Mat. Zamet., 5, No. 5, 561–568, 1969 [Russian]. Translated in Math. Notes Acad. Sci. USSR, 5, No. 5, 336–340, 1969.
[5] S. S. Marchenkov, On bounded recursions, Math. Balk., 2, 124–142, 1972 [Russian].
[6] S. S. Marchenkov, Bases under superposition in the classes of recursive functions, Matematicheskie voprosy kibernetiki (Mathematical Problems of Cybernetics), Vol. 3, pp. 115–139, Nauka, Moscow, 1991 [Russian].
[7] S. S. Marchenkov, Superpositions of elementary arithmetical functions, Disret. Anal. Issled. Oper., 13, No. 4, 33–48, 2006 [Russian]. Translated in J. Appl. Ind. Math., 1, No. 3, 351–360, 2007.
[8] S. S. Marchenkov, Elementarnye arifmeticheskie funktsii (Elementary Arithmetical Functions), LIBROKOM, Moscow, 2009 [Russian].
[9] S. S. Marchenkov, Bounded monotonic recursion and multihead automata, Program., No. 6, 3–11, 2013 [Russian]. Translated in Program. Comput. Softw., 39, No. 6, 301–308, 2013.
[10] S. S. Marchenkov, On elementary word functions obtained by bounded prefix concatenation, Diskretn. Mat., 27, No. 3, 44–55, 2015 [Russian]. Translated in Discrete Math. Appl., 26, No. 3, 155–163, 2016.
[11] S. S. Marchenkov, Klassy elementarnykh rekursivnykh funktsii (Classes of Elementary Recursive Functions), FIZMATLIT, Moscow, 2016 [Russian].
[12] K. V. Osipov, On quasi-universal word functions Vestn. Mosk. Univ., Ser. 15, No. 1, 28–34, 2016 [Russian]. Translated in Mosc. Univ. Comput. Math. Cybern., 40, No. 1, 28–34, 2016.
[13] L. Kalmár, Egyszerü példa eladönthetetlen aritmetikai problémára, Mat. Fiz. Lapok, 50, 1–23, 1943 [Hungarian].
