|
This article is cited in 6 scientific papers (total in 6 papers)
On elementary word functions obtained by bounded prefix concatenation
Sergey S. Marchenkov Moscow State University
Abstract:
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.
Keywords:
bounded prefix concatenation, polynomially computable function.
Received: 14.04.2015
Citation:
Sergey S. Marchenkov, “On elementary word functions obtained by bounded prefix concatenation”, Diskr. Mat., 27:3 (2015), 44–55; Discrete Math. Appl., 26:3 (2016), 155–163
Linking options:
https://www.mathnet.ru/eng/dm1334https://doi.org/10.4213/dm1334 https://www.mathnet.ru/eng/dm/v27/i3/p44
|
Statistics & downloads: |
Abstract page: | 431 | Full-text PDF : | 180 | References: | 60 | First page: | 31 |
|