On quasi-universal word functions

被引：0
作者：
Osipov K.V. [1 ]
机构：
[1] Department of Computational Mathematics and Cybernetics, Moscow State University, Moscow
来源：
Moscow University Computational Mathematics and Cybernetics | 2016年 / 40卷 / 1期
关键词：
Quasi-universal function; word functions;
D O I：
10.3103/S0278641916010040
中图分类号：
学科分类号：
摘要：
A method for constructing quasi universal “simple form” functions in the class of word functions is proposed. The method is used to construct an explicit superposition basis in the class of functions that can be computed in polynomial time. © 2016, Allerton Press, Inc.
引用
收藏
页码：28 / 34
页数：6
相关论文
共 4 条
  • [1] Grzegorczyk A., Some classes of recursive functions, Rozpr. Math., 4, pp. 1-46, (1953)
  • [2] Rodding D., Über die Eliminierbarkeit von Definitionsschemata in der Theorie der rekursiven Funktionen, Z. Math. Logik Grundlagen Math., 10, pp. 315-330, (1964)
  • [3] Marchenkov S.S., Elimination of recursion schemas in the Grzegorczyk %2 class, Math. Notes, 5, pp. 336-340, (1969)
  • [4] Volkov S.A., An example of a simple quasi-universal function in the class %2 of the Grzegorczyk hierarchy, Discrete Math. Appl., 16, pp. 513-526, (2006)
1