Том 24, номер 4, 2017 г., Стр. 60-76

УДК 519.716
Марченков С. С.
Об операциях ограниченного суффиксного суммирования и мультиплицирования

Аннотация:
Вводятся операции ограниченного суффиксного суммирования и ограниченного суффиксного мультиплицирования. На основе этих операций определяется класс BSSM полиномиально вычислимых функций. Доказывается, что класс BSSM включает класс BPC, определяемый на основе операции ограниченной префиксной конкатенации, и имеет конечный базис по суперпозиции.
Библиогр. 13.

Ключевые слова: ограниченное суффиксное суммирование, ограниченное суффиксное мультиплицирование.

DOI: 10.17377/daio.2017.24.558

Марченков Сергей Серафимович ¹
1. Московский гос. университет им. М. В. Ломоносова,
Ленинские горы, 1, 119991 Москва, Россия
е-mail: ssmarchen@yandex.ru

Статья поступила 30 ноября 2016 г.

Литература

[1] Волков С. А. Пример простой квазиуниверсальной функции в классе $\mathscr E^2$ иерархии Гжегорчика // Дискрет. математика. 2006. Т. 18, № 4. С. 31–44.

[2] Мальцев А. И. Итеративные алгебры и многообразия Поста // Алгебра и логика. 1966. Т. 5, № 2.
С. 5–24.

[3] Мальцев А. И. Итеративные алгебры Поста. Новосибирск: Изд-во НГУ, 1976. 100 с.

[4] Марченков С. С. Устранение схем рекурсий в классе $\mathscr E^2$ Гжегорчика // Мат. заметки. 1969. Т. 5, № 5. C. 561–568.

[5] Марченков С. С. Об ограниченных рекурсиях // Math. Balk. 1972. T. 2. C. 124–142.

[6] Марченков С. С. Базисы по суперпозиции в классах рекурсивных функций // Мат. вопросы кибернетики. 1991. Вып. 3. С. 115–139.

[7] Марченков С. С. Суперпозиции элементарных арифметических функций // Дискрет. анализ и исслед. операций. Сер. 1. 2006. Т. 13, № 4. С. 33–48.

[8] Марченков С. С. Элементарные арифметические функции. М.: Либроком, 2009. 47 с.

[9] Марченков С. С. Ограниченная монотонная рекурсия и МГ-автоматы // Программирование. 2013. № 6. С. 3–11.

[10] Марченков С. С. Об элементарных словарных функциях, получаемых на основе ограниченной префиксной конкатенации // Дискрет. математика. 2015. Т. 27, № 3. С. 44–55.

[11] Марченков С. С. Классы элементарных рекурсивных функций. М.: Физматлит, 2016. 136 с.

[12] Осипов К. В. О квазиуниверсальных словарных функциях // Вестн. Моск. ун-та. Сер. 15. Вычисл. математика и кибернетика. 2016. № 1. С. 28–34.

[13] Kalmár L. Egyszerü példa eladönthetetlen aritmetikai problémára // Mat. Fiz. Lapok. 1943. Köt. 50.
Ol. 1–23.