On elementary word functions obtained by bounded prefix concatenation. (English. Russian original) Zbl 1521.03116
Discrete Math. Appl. 26, No. 3, 155-163 (2016); translation from Diskretn. Mat. 27, No. 3, 44-55 (2015).
Summary: The operation of bounded prefix concatenation (BPC) is introduced on the set of word functions in the alphabet \(\{1, 2\}\). The class BPC of polynomially computable functions is defined on the basis of this operation and the superposition operation. The class BPC is shown to contain a number of word functions and to be closed with respect to certain known operations. A certain type of two-tape nonerasing Turing machines is introduced, functions from the class BPC are shown to be computable on machines of this type in polynomial time.
MSC:
| 03D20 | Recursive functions and relations, subrecursive hierarchies |
| 03D15 | Complexity of computation (including implicit computational complexity) |
| 03D10 | Turing machines and related notions |
References:
| [1] | Kuznetsov A. V., “On a theorem on the canonical form for ordinal recursive functions”, Supplement to: R. L. Goodstein, Mathematical logic, Inostrannaya Literatura, 1961, 149-154 (in Russian).; Kuznetsov, A. V., Mathematical logic, 149-154 (1961) |
| [2] | Marchenkov S. S., Elementary recursive functions, MCCME, Moscow, 2003 (in Russian), 112 pp.; Marchenkov, S. S., Elementary recursive functions, 112 (2003) |
| [3] | Marchenkov S. S., “Limited monotonous recursion and MG-automata”, Programming, \(2013, {{\rm{N}}^{\underline{o}}} 6, 3-11\) (in Russian).; Marchenkov, S. S., “Limited monotonous recursion and MG-automata”, Programming, 3-11 (2013) |
| [4] | Grzegorczyk, A., “Some classes of recursive functions”, Rozpr. Matemat., 4 (1962), 1-46.; Grzegorczyk, A., “Some classes of recursive functions”, Rozpr. Matemat, 4, 1-46 (1962) · Zbl 0113.00601 |
| [5] | Kalmar, L., “Egyszerü pelda eldonthetelen aritmetikai problemara”, Mat. és fiz. lapok, 50 (1943), 1-23.; Kalmar, L., “Egyszerü pelda eldonthetelen aritmetikai problemara”, Mat. és fiz. lapok, 50, 1-23 (1943) |
| [6] | Skolem, Th., “Proof of some theorems on recursively enumerable sets”, Notre Dame J. Formal Logic, 3:2 (1962), 65-74.; Skolem, Th., “Proof of some theorems on recursively enumerable sets”, Notre Dame J. Formal Logic, 3, 2, 65-74 (1962) · Zbl 0060.08906 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
